Page 1 of 1

11457 - Classified

Posted: Tue Jun 24, 2008 10:29 pm
by baodog
I tried constructing RMQ from DFS tree of each node with no parents.
However this TLEs, since there can be O(n) such RMQs.
Is there some way to do it with one RMQ, so each query is O(logn)?
How did you guys solve this one :-) ? Thanks!

Re: 11457 - Classified

Posted: Wed Jun 25, 2008 1:01 am
by baodog
maybe construct one RMQ, keep list of indices for each node, and find the closest two nodes by binary search.

Re: 11457 - Classified

Posted: Wed Jun 25, 2008 4:18 am
by rio
This problem is about finding LCA in DAG.

I used an algorithm with O(nm) for precalculation and O(1) for query.
-----
Rio

Re: 11457 - Classified

Posted: Wed Jun 25, 2008 6:03 am
by baodog
THanks. Do you have a reference? Can you describe your algorithm? Thanks!

Re: 11457 - Classified

Posted: Wed Jun 25, 2008 6:29 am
by rio
Search google with "lca dag".
I found paper about it in the first page.
-----
Rio