memeset's blog

Debugging help on a lca problem
By memeset, history, 8 years ago, In English

Hello everyone. If anyone would be kind enough to help me debug my code to this problem I would appreciate it very much :) I would like it very much if I could AC this problem since I am very tilted by it right now as I have no idea why it's wrong :/ Thanks everyone!

  • Vote: I like it
  • -2
  • Vote: I do not like it

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

Sorry, I should probably mention a few things about the code to help clear it up a bit:

dp is the array used for binary jumping for finding the kth ancestor subsum[i] is the number of nodes the ith subtree has, excluding itself lcac(x, y) returns the children of the lca of x and y that are on the path from x and y to lca of x and y.

I think it's the else part of the for loop that's causing the error but I'm not sure.

Thanks!

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

Here is your fixed solution. Don't use log2 because it returns double value.

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

    Ah, I see, thanks!

    So, just to clarify, is it a precision error because of the log2? Because, theoretically, it should be fine because it rounds down to the int, right? Or am I missing something?

    → Reply