In the last CSAcademy Round 53, Problem Number C, My this submission gives me TLE
But after the contest I have changed my code and submitted and that was accepted.
The change was on line 144 and 161. On the first code (TLE) I checked if the propagate value is not equal to 0 by the following code
if( tree[node].prop )
On the accepted code I checked the same thing by this following code:
if( tree[node].prop != 0 )
But I think there is no difference in the two codes. Please explain me if I am wrong.
I have already posted on CSAcademy. But haven't got any reply till now. So I posted here for getting more response. You can check my blog by the following link: My Blog on CSAcademy
Your AC solution runs in 912ms. I resubmitted your TLE solution and it was accepted. Run time might differ slightly even if the code stays exactly the same.
I didn't see someone so unlucky :(
Actually the intended solution is O(n), while your solution is O(nlog2(n)). So you are pretty lucky that your second solution passed :P
n = 100000, log(n) = 17, nlog2(n) = 17*17*100000 = 2.89*10^7, I think it can run in 1 second theoretically. Right?
You're right, I didn't check the constraints, just the complexity.
Now you should agree with me :p — I didn't see someone so unlucky!!
BTW, thanks for your help. It saves my night sleep. :)