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.