Time limit

Hello everyone. I always receive time limit on Test №21. Could you give any hints? Maybe this task requires special data structure (I try to represent tree as list of edges or adjacency list) or there is interesting algorythm? Thanks for reading.

Re: Time limit

Not update connected vertexes for vertexes with amount of connections more than Sqrt(N).

In this case sum for vertex will be current sum + delta for connected vertexes with size more than Sqrt(N).

Re: Time limit

I have the same problem with TLE #21 and I can't understand your hint: what's that 'delta', how can I track/calculate it?

I realize that the bottleneck is in vertices with high amount of linked edges but I can't understand how to avoid them - I still need update all vertices, otherwise I loose data for next steps.

Re: Time limit

yes, you're right about data structure. I used binary indexed tree to solve the problem. Overall complexity is O(n + m * logn). So, you actually preprocess data in O(n) time and for each query you spent O(logn) time, which perfectly fits time constraints of the problem

Re: Time limit

my algo is O(n+m)

Re: Time limit

Posted by

Sunnat 15 Jan 2015 16:33

I agree with you