Во время Codeforced Round #174 в задаче 284D - Коровки программируют мое решение не прошло системные тесты. Я использовал DFS алгоритм с запоминанием (как и в разборе задач), поэтому сложность линейная. Но я получил TLE на тесте #12. См. 3341733.

На дорешивании, я сделал только следующие изменения в моем коде:

1) Первый узел не кладется в стек.

2) Отредактирован следующий блок (после первого изменения это стало возможно, без этого изменения — тоже TLE на тесте 12)

                int cur = S.top();
                if ( cur >=2)
                {
                    res[cur] = ans;
                }

заменен на

                int cur = S.top();
                res[cur] = ans;

После этого я получил AC, но время очень близко к Time Limit: 1968 ms. См. 3344711

Я видел, что сдают эту задачу за меньше, чем 1 сек. Я не могу понять, почему моя программа имеет большой коэффициент в линейной сложности, и на чем она долго исполняется.

Если кто-нибудь поможет мне разобраться, я буду очень благодарен.