LaughIsLife's blog

SPOJ-QTREE2
By LaughIsLife, 10 years ago, In English

I am trying to solve this problem but getting Wrong Answer again and again. I can't find my mistakes. Please help me to find out my mistakes or give me some test cases in which my code can't pass. Here is my code: http://codepad.org/c3DScA3P

Thanks in Advance!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

I hope you know how to find LCA with sparse table or segment tree. That's how to compute the distance between two nodes. When you use RMQ you have to give new numbers to the nodes and store the position where each node appears for first time. This time you can store all positions for each node using vectors. So if you have query KTH a b k just do this:

Assume that a appears first. Use binary search to find the rightmost position of a which is on the left side of b's first appear. Then print the k-th node after this position.

Edit: I was unable to see your code and I just told you my idea.

→ Reply