prodipdatta7's blog

Help!!!
By prodipdatta7, 6 years ago, In English

Problem: 13101 — Tobby On Tree

Solution: Using HLD or Using HLD

The problem is, You are given a tree. In every node, there is a value assigned to it and also given some query.

Query:

1 u v: compute the gcd on the path from u to v.

2 u x: Change the value of the node u to x.

I have written a code of HLD and submitted but it gave me TLE. I haven't found anything in the code to optimize.

In this case, I need help to optimize the code if it is possible. Please help me if you are free.

Thanks in Advance :)

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I haven't found anything in the code to optimize.

What have you tried in the first place? Have you tried random test cases? Have you tried benchmarking certain functions in your code?

Your code is over 150 lines long and is very complex. So I doubt anyone is going to read it.

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

    Thanks for the comment.

    I have tried random test cases but there is no problem in the result. As the problem is how to reduce the complexity of my code, I can't figure out the way in which the code will be more efficient than before.

    → Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I guess the problem may be with fresh() function. There may be so many test cases with n is small in each and you are resetting $$$1.5*10^5$$$ values to something. I don't see any potential TLE risk on HLD and segment tree part.

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

    I have updated my fresh() function but nothing much improved :(

    fresh()
    → Reply