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 costinto 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](https://mirror.codeforces.com/contest/1955/problem/G).↵
↵
Eg example accepted solution: https://mirror.codeforces.com/contest/1955/submission/260714562↵
vs TLE solution with declaration inside loop: 260714503 (recommend using CF compare)
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
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](https://mirror.codeforces.com/contest/1955/problem/G).↵
↵
Eg example accepted solution: https://mirror.codeforces.com/contest/1955/submission/260714562↵
vs TLE solution with declaration inside loop: 260714503 (recommend using CF compare)
