C++ Declaring vector inside loop = TLE?

Revision en2, by Jomax100, 2024-05-13 00:25:33

Why does declaring vector inside of the loop result in TLE. Eg

Outside

vector<int> visited(n);
for(){
  visited.assign(n, 0);
  // other code;
}

Inside

for(){
  vector<int> visited(n);
  // other code;
}

In the problem below, the "outside" method is AC with 765ms, but the "inside" method is TLE at 3000ms.

Why? I can understand there must be some extra cost to re-allocate and de-allocate memory for the vector, but is the constant factor really that high? Time Complexity is the same (size of the vector), so I was quite surprised. Would be great if anyone can share more insights. Thanks!

Context: I was working Codeforces Round 938 (Div. 3), problem G: GCD on a grid.

Eg example accepted solution: https://mirror.codeforces.com/contest/1955/submission/260714562 vs TLE solution with declaration inside loop: 260714503 (recommend using CF compare)

Tags c++, constant factor, allocation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Jomax100 2024-05-13 00:25:33 12
en1 English Jomax100 2024-05-13 00:23:45 1004 Initial revision (published)