litvinas's blog

Codeforces time limit exceeded problem?
By litvinas, history, 9 months ago, In English

Hello Codeforces, I have been working on the problem 1176E - Покрывай! and submitted the following code: 248930264 (I submitted many but I felt this one was the closest to go through) My time complexity was the standard O(N + M) N vertices M edges but couldnt get the code through however I found a similar code 248919921 which got Accepted with the same time complexity and simmilar constant factors What is the difference between the codes / why did my code tle?

thank you in advance litvinas

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Write bool vis[n + 1] & bool mark[n + 1] instead of 2e5

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

    That worked,Thank you

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

      I hope u understood the reason too y it got accepted...

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

    Nice. Can you explain how does it impact that please?

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Hii , as far as I understand declaring array of size 2e5 [which means running a loop of size 2e5] for each input would result us in performing > 1e7 operations for large number of testcases [i.e. t] where the values of n & m are small [for them to be within constraint limit] , hence by using bool vis[n + 1] & bool mark[n + 1] we use the fact that ∑m≤2⋅105

      → Reply