|
|
back to boardHello 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. 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). 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. 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 |
|
|
