akcode_121's blog

lowest common ancestor on spoj getting TLE
By akcode_121, history, 8 years ago, In English

I stuck at a problem lca,I tried to solve it using square root decomposition Here is my implementation https://ideone.com/Q6AbaO

processing time O(n)

query time O(sqrt(n))

Result: Getting TLE

But when i read comments on spoj most of people O(n) query was accepted. Can any one tell me where I am doing wrong?

My code is very well explained here with every line of code https://www.geeksforgeeks.org/sqrt-square-root-decomposition-set-2-lca-tree-osqrth-time/

  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Try binary lifting. It has a query time of O(logN). I really liked Errichto's tutorial on it.

→ Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The adjacency list is not cleared at the end of each testcase, so there might be cycles in the graph formed by the union of the trees in all testcases.

→ Reply