LunaticPriest's blog

LCA using Binary Lifting
By LunaticPriest, history, 4 years ago, In English

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!

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

Comments Comments (11)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

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

    He doesn't reset on each query, he reset on each test case ...

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

      Sorry, that is what I meant. Fixed.

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

        Okay, but he is not reseting 10005*20 on each testcase, he is reseting n*20 on each testcase, if the sum of n * 20 is not enough to solve in TL, it cant be solve with this code anyway

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

          I probably should go to sleep, but lines 23 — 27 indicate otherwise.

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

Hello,

Do take a look at line 65 :D

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

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

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

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

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

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

        I will do this every time I encounter such problems. thanks for the advice!

        → Reply