Problem Link : https://cses.fi/problemset/task/1750 Submission Link : https://cses.fi/paste/f2a12df5ba1948a496b5bf/
I am not sure why my code this TLE on one test case (where N and Q are 10^5). I tried doing it using binary Lifting , The matrix A is used to store descendants at 2^j position where j<= 35
I believe the solution should not take more then O(q*35+35*n) steps.
Can someone Please help me out?
Auto comment: topic has been updated by alyosha (previous revision, new revision, compare).
Don't use <<endl, it's too slow, instead use "\n". (with this change I believe it should pass)
I tried changing it to "\n" , it's still failing that one test case due to TLE, even when I run this code on my local device it takes 2 seconds. Something is definitely wrong in the code Just I can't figure it out.
Use array instead of vector, as the constant factor of vector is quite high. I've tried to change to array and got AC (it just barely fits the TL though).
Hey thanks, it worked just right. I even remember your userName as I see it often in comments of contest editorials. Thanks a lot for the help.
Accepted Code with the TLE test passing in 0.59s (used an array instead of a vector) : Submission. Same code passes with 0.99s if I use a vector.
The changes I made :
Used \n instead of $$$endl$$$
changed the binary lifting part, just iterate thru the bits in $$$K$$$ instead of starting from 34 everytime (kinda matters coz the time limit in CSES is just too tight)
added cout.tie(NULL) in the fast io part (might matter coz the printing part is kinda heavy)
try experimenting with other changes as well, might end up learning something new :)
Thank you I will make change of '\n' to endl and cout.tie(NULL) in my codeforces template as well.