During Codeforces Round 987 (Div. 2), I got Runtime Error on Test Case 59 (in Problem E. Penchick and Chloe's Trees). It shows Stack Overflow Error! But, the same code got AC on C++17 while upsolving!
- C++20 Submission: 291655589 — Runtime Error on TC 59
- C++23 Submission: 291671738 — Runtime Error on TC 61
- C++17 Submission: 291671684 — AC
But, after a little modification on insider loop, it got AC in C++20: 291668944. But, I couldn't find any valid reason for stack-overflow, and how this submission solved this error!
Can you help me?
It is stack overflow. To compile C++23 solutions, Codeforces uses the following command:
g++ -Wall -Wextra -Wconversion -static -DONLINE_JUDGE -Wl,--stack=268435456 -O2 -std=c++23 program.cpp -lstdc++exp
-- it gives 256 MiB for stack. But for this program it is not enough. 450 MiB fixes the issue: 291681903. I'd say that on a 32-bit architecture, the pointer consumes less memory, which is why there is enough stack.Thanks!
But, what's about the modified code I've mentioned in the post? That code got AC on C++20, with no large change in code!
You made
mp
andperm
global, it reduced stack memory consumption.It seems G++ 13.2 and 14.2 may preallocate the stack, for the above program, apparently the stack usage should be 128MB (2 calls of
dfs
, each results 64MB allocation), which conforms G++ 7.3 behavior. But with 13.2 and 14.2, the memory usage is 192MB, which seems it allocates when entering adfs
regardless if the variables are used or not.Also the size of
vector<ll>
map<ll, ll>
set<ll, greater<ll>>
gets doubled in the 64-bit version to 24, 48, 48. Suppose the above preallocation is true, then each call of dfs results 24+48+48+100ish(function call and parameter)=220B, when multiplied 1e6, it's close to 256MB. If add some misc things, that could be an overflow.