vaishali614's blog

LCA Problem — Binary Lifting
By vaishali614, history, 4 years ago, In English

Hello! I tried to solve this problem on SPOJ. Here is my solution. Its showing TLE. Can anyone please help solving this? Thanks

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

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

log2() returns a double. Try __lg().

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but i'm getting TLE, not WA.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yeah, you could be sitting in that while loop on line 49 infinitely if log2() gets rounded the wrong way. In any case, loops like that are scary, and I would certainly try to change it to a for loop if possible, especially if I was getting TLE. Take a look at how the loop is done here.

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

It is multiple testcases, you should clear() your tree before each one. Or better, do not use global variables.

→ Reply