Блог пользователя memeset

Debugging help on a lca problem
Автор memeset, история, 8 лет назад, По-английски

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!

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить