Hello everyone,
For the recent codeforces round #381, I submitted this code for the div2D/div1B question here. I am not sure why it is wrong...
The basic idea of my code was that I use binary lifting to store the 2^kth ancestor and the distance to the 2^kth ancestor in bparent[][] and bdist[][]. I then binary search for the highest ancestor that each node is controlled by and store the starting and ending points in event[], which i can just dfs and sum up in my function solve().
Could somebody please tell me where I went wrong in my code? Any help would be appreciated.
Thanks!
I think your problem might be with your use of the level. I don't think that's necessary. The part "if ((1 << j) <= level[i] && sum + bdist[curr][j] <= a[i])" doesn't make much sense to me. I didn't use the level of the nodes in my code and I got AC. http://mirror.codeforces.com/contest/740/submission/22481099
I commented that part out and I got WA on the sample case :/. I'm using level because I want to check if the j (well, 2^j) that I'm on exceeds the depth of the current node. If it does, then that 2^j is useless and I move to the next 2^j.
It's easier to set the root to be looped to itself with weight=0. You don't need the level[] array at all (and dfs()). Here is your code simplified and AC 22515158. Though I don't know where exactly is the mistake in your code.
I think the mistake may have been the event[parent[i]]++ and event[parent[curr]]-- which you changed to event[i]++ and event[curr]--. May I ask, why was it changed to that?
If I understand correctly, curr is the last node that still controls i, so wouldn't you want to do parent[curr] to get the first node that does not control curr, to subtract it out there? Also, i does not control itself, so wouldn't you want to do event[parent[i]]++?
Also, very cool trick with looping the root to itself :)
I also changed the order in solve():
Thus, the modifier is added afterwards.
Ah, I see. I also had to add a if (curr != 1) for my code and then I got AC. Not sure where the bug is, probably has something to do with the level[] I guess.
Thanks for your help!