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!
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
Can it give TL because you reset $$$10005 \cdot 20$$$ values in the precompute function on each testcase?
He doesn't reset on each query, he reset on each test case ...
Sorry, that is what I meant. Fixed.
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
I probably should go to sleep, but lines 23 — 27 indicate otherwise.
oh, sorry, you are right!
Hello,
Do take a look at line 65 :D
I can't believe it... Thanks for the bug fix that took me hours :(
It's always helpful to try tests with $$$t \gt 1$$$
They help you find bugs involving typos like this, resetting arrays etc..
I will do this every time I encounter such problems. thanks for the advice!