Mohammed-Shoaib's blog

By Mohammed-Shoaib, 5 years ago, In English

I was trying to solve the following problem: 1106B - Лунный новый год и заказ еды and I noticed something interesting. Below are two solutions:

Solution [1]
Solution [2]

Both the solutions are pretty much the same except Solution [1] uses a function call findCheapest and Solution [2] has the raw code replacing the function call. However, Solution [1] causes a TLE on test 9 taking 2000 ms whereas Solution [2] gets accepted and takes 140 ms. This means Solution [2] is atleast 14× faster than Solution [1].

At first I thought the priority_queue might be causing some issues. But I am passing the address as you can see, so the function should be modifying the same location.

I always thought function calls do not affect the running time much. Does this mean function calls play a big role in the running time? Could someone explain to me why this could have happened?

P.S. I am pretty much a noob so please feel free to correct anything and sorry for any stupid mistakes.

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

»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

It's not directly the function calls, you are passing a by value, pass it by (const) reference instead (https://codeforces.com/contest/1106/submission/49777019)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Oh wow, I mean I know passing by value would mean it ends up creating a copy of the variable but I did not expect it to cause a TLE because of that. Thank you for your reply!