By adamant, history, 15 months ago, ,

Okay, so compare these two submissions: 51053654 and 51053605

The only difference is that first one made via GNU C++17 and the second one via MS C++ 2017. Code is same, but first gets RE 16 and second one gets AC.

WTF, GNU C++??

• +102

 » 15 months ago, # |   +8 UB maybe?
•  » » 15 months ago, # ^ |   +8 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
 » 15 months ago, # |   0 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.
•  » » 15 months ago, # ^ |   0 Is it really stack overflow? Stack on codeforces is 256 mb: Link
•  » » » 15 months ago, # ^ |   +8 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?
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +8 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
•  » » » » 15 months ago, # ^ |   +8 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
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +19 So, as we discussed with adamant elsewhere, the problem was indeed in the stack size.AC submission: 51059986So 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
•  » » » » 11 months ago, # ^ | ← Rev. 6 →   +21 Everything is fine with -O1 flag for C++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 ). Submission
 » 15 months ago, # | ← Rev. 3 →   0 same thing((( 51079321 51026165.Didn't think about stack size
 » 14 months ago, # |   0 Hi, please compare these two submissions: 51586126 and 51586141. The only difference is that the first one adding the inline specifier onto the tarjan function and gets AC, the second one without inline gets RE 16.Any ideas?
•  » » 14 months ago, # ^ |   +8 idk, may be you overflowed the stack