ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2030. Awesome Backup System

Time limit
Posted by Snowball_TverSU 22 Nov 2014 23:49
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
Posted by Tolstobrov Anatoliy[Ivanovo SPU] 3 Dec 2014 20:47
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
Posted by Mikhail Krivenko 6 Dec 2014 01:01
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
Posted by daniel_de_darik 6 Dec 2014 17:03
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
Posted by Adhambek 30 Dec 2014 17:58
my algo is O(n+m)
Re: Time limit
Posted by Sunnat 15 Jan 2015 16:33
I agree with you