LunaticPriest's blog

LCA using Binary Lifting
By LunaticPriest, history, 7 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?
»
7 years ago, hide # |
← 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
»
7 years ago, hide # |
← 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
»
7 years ago, hide # |
 
Vote: I like it +37 Vote: I do not like it

Hello,

Do take a look at line 65 :D

→ Reply