Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### LunaticPriest's blog

By LunaticPriest, history, 7 months ago, ,

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

 » 7 months ago, # | ← Rev. 2 →   +2 Can you share the link to the problem that you were testing your code with? It would help to debugPS: for example, if the given graph is not a DAG rooted at node 1, your DFS is wrong, because you are visiting your parent
•  » » 7 months ago, # ^ |   0 Here is the link to the problem. Hope it helps.
 » 7 months ago, # | ← Rev. 2 →   +3 Can it give TL because you reset $10005 \cdot 20$ values in the precompute function on each testcase?
•  » » 7 months ago, # ^ |   +8 He doesn't reset on each query, he reset on each test case ...
•  » » » 7 months ago, # ^ |   +3 Sorry, that is what I meant. Fixed.
•  » » » » 7 months ago, # ^ |   +8 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
•  » » » » » 7 months ago, # ^ |   +3 I probably should go to sleep, but lines 23 — 27 indicate otherwise.
•  » » » » » » 7 months ago, # ^ |   +8 oh, sorry, you are right!
•  » » » » » » » 7 months ago, # ^ |   0 The problem is: I don't even get TLE, I get WA. By the way, the graph is a DAG rooted at 1, and there are many people who solved the problem using binary lifting. I still couldn't find the bug ;(
 » 7 months ago, # |   +37 Hello,Do take a look at line 65 :D
•  » » 7 months ago, # ^ |   +14 I can't believe it... Thanks for the bug fix that took me hours :(
•  » » » 7 months ago, # ^ |   +8 It's always helpful to try tests with $t > 1$They help you find bugs involving typos like this, resetting arrays etc..
•  » » » » 7 months ago, # ^ |   +11 I will do this every time I encounter such problems. thanks for the advice!