burtmacklin's blog

Need help in DIV 2 #660 : Problem C
By burtmacklin, history, 4 years ago, In English

Hi,

I am getting TLE at test case 6. I have added documentation to improve readability.

Things I have tried:

  1. Check for infinite loops : Not possible since I am keeping track of every node visited.
  2. Check time complexity : It is O(n), which should be enough for 2 second limit.
  3. Replace cin and cout with scanf and printf : Didn't work.

Thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

You are passing vectors by value, which result in creation of vector in every function calls, making runtime be O(n2). Either pass it by reference or make them global.

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

    Thanks Just_a_programmer! It is accepted now after making them global.

    I will try to read up on these C++ details further. However, if passing by value was the concern, it should have been a memory issue (assuming that program was somehow crossing the memory limit) instead of execution time issue, right?

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

      No. When you pass by value, the vectors (or arrays) are copied, and for large vectors, it'll take a lot of time and result in TLE!

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      When we pass by value vector is copied, it requires time as well as memory, but in most cases the memory limit is more then enough for the purpose.

      → Reply