During CF Round #174 on 284D - Cow Program my algorithm didn't passed system tests. I used DFS algorithm with memorization (as in Editorials), so complexity is linear. But I got TLE in test #12. See 3341733.
In practise, I just made the following changes in my code:
1) First node isn't pushed to stack.
2) Edited this block (it's possible after first change, without this change — still TLE on test# 12)
int cur = S.top();
if ( cur >=2)
{
res[cur] = ans;
}
to
int cur = S.top();
res[cur] = ans;
After this I got AC, but time is very close to TL: 1968 ms. See 3344711
I saw that users have solved this problem with time less than one second. I don't understand why my program has big constant in linear complexity, and where is performance overhead in my program.
If anyone can help me, I will thank you ever so much.