babu1998's blog

TLE — DSU on Trees
By babu1998, history, 4 years ago, In English

https://www.codechef.com/problems/CHEFCOMP

https://www.codechef.com/viewsolution/37171940

I cant understand why am i getting TLE even after applying all optimisations of DSU. Please help. I have tried this for question for 3 days.

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

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

Try path compression https://cp-algorithms.com/data_structures/disjoint_set_union.html#toc-tgt-2

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

    I have tried path compression in my submission

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

      That's not path compression you are elevating it by only one level try this 

      ll find(ll i)
{
    
    if(parent[i]==i)
    return i;
    return parent[i] = find(parent[i]);
}
      → Reply