# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
UB maybe?
Can you see any? For me code seems pretty clear. I'd rather expect that somehow they optimize code differently which leads first one in stack limit. It's not very realistic though because I had a GCC version running into TL 18 (thus passing 16th test): 51022745
If depth of your dfs may be >= 1e6, then it's stack overflow. And in that case "WTF" can be easy explained by different stack size or/and different bytes-on-stack-per-recursive-call used by the compiler.
Is it really stack overflow? Stack on codeforces is 256 mb: Link
Note that test 16 is one of the test where memory consumption is maxed for your MSVC solution and it's >400mb with GCC. So maybe you actually use more than 256mb of stack in that case?
What is actual max depth of recursion? If I interpret these submissions correctly: 51057215 51057182, 1 level of recursion eats 28 bytes on msvc and 64 bytes on GCC
So, If I interpreted it correctly, the depth is 5e6 and so with msvc you use ~150mb+28*5e6=~290mb. with gcc you use 320mb of stack
So, as we discussed with adamant elsewhere, the problem was indeed in the stack size.
AC submission: 51059986
So the problem can be avoided by creating new stack with increased max stack size. You can copypaste snippet at the end of the code to your template to forget about the stack size
--
One open question is why gcc require two times more memory
Everything is fine with
-O1
flag forC++17
, adamant AC submissionI thought that with
-Os
will be fine too, but it is notSo I think that something from
-O2
optimizations activates aligning on system stack by 64 bytes.UPD. Option
-fconserve-stack
with-O3
can be used, it gave 313 MB memory usage (~ 163 MB stack) and runtime is 3181 ms, faster than original solution on MSVC ( 3524 ms ), and faster than -O1 solution ( 3681 ms ). Submissionsame thing((( 51079321 51026165.
Didn't think about stack size
Hi, please compare these two submissions: 51586126 and 51586141. The only difference is that the first one adding the
inline
specifier onto thetarjan
function and gets AC, the second one withoutinline
gets RE 16.Any ideas?
idk, may be you overflowed the stack