sujal22514's blog

CSES Planet Query — 1
By sujal22514, history, 4 hours ago, In English

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?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sujal22514 (previous revision, new revision, compare).

→ Reply
»
4 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

Don't use <<endl, it's too slow, instead use "\n". (with this change I believe it should pass)

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 hours ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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).

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
4 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you I will make change of '\n' to endl and cout.tie(NULL) in my codeforces template as well.

    → Reply