memeset's blog

Help please! Why is it wrong (Round #381 div2 D)
By memeset, history, 8 years ago, In English

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!

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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 :)

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          I also changed the order in solve(): 

          return ans[node] + event[node];

          Thus, the modifier is added afterwards.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            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!

            → Reply