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

Автор LunaticPriest, история, 4 года назад, По-английски

Hello, the mightly CodeForces community! It's me with another question because there are only 4 days left until the Turkey Olympiad in Informatics!!! I am trying to write the code that finds the LCA of 2 nodes with NlogN precomputation and logN per query. All the trees that I tested my code against, and all the corresponding edge cases give the correct output, so I don't really know where to fix. I've been debugging it for hours now :( Here is the code. I appreciate all your help, and I promise I will try to do my best to understand and implement your ideas!

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Can you share the link to the problem that you were testing your code with? It would help to debug

PS: for example, if the given graph is not a DAG rooted at node 1, your DFS is wrong, because you are visiting your parent

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Can it give TL because you reset $$$10005 \cdot 20$$$ values in the precompute function on each testcase?

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

Hello,

Do take a look at line 65 :D

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    I can't believe it... Thanks for the bug fix that took me hours :(

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

      It's always helpful to try tests with $$$t > 1$$$

      They help you find bugs involving typos like this, resetting arrays etc..