ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1329. Galactic History

Why WA6?
Posted by GastonFontenla 24 Aug 2015 08:42
My algorithm:

I run BFS to assign levels (DISTANCE TO THE ROOT) to each node.

Then, when read the queries:
If the level of both nodes are the same, no exist any path between them. Answer is 0
If the level of qA is less than level of qB, maybe exist a path between them. Find it.
If found a path, Answer is 1
If no path had been found, and the level of qA is greater than level of qB, Find a path.
If found a path, Answer is 2
If none of the previous worked, the answer to the querie is 0.


I read that it could be solved with LCA, but I think that it's better and elegant algo.
Please help me. Maybe my algo is right, but my problem may be on the code. If need to see code, i'll post it.
Re: Why WA6?
Posted by GastonFontenla 9 Sep 2015 20:19
Okey, I solved it :D got AC, but the solution was rejudged. Now is TLE