Во время 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 сек. Я не могу понять, почему моя программа имеет большой коэффициент в линейной сложности, и на чем она долго исполняется.
Если кто-нибудь поможет мне разобраться, я буду очень благодарен.
Взял оригинальное ТЛ-решение.
3345872 — первый простой оптимайз, избавился от потери кучи времени на cin/cout, код прошел за 1.875.
3345902 — второй простой оптимайз, избавляемся от квадратического количества работы с памятью (O(n) раз вектор flag размера О(n)), проходит за 0.499.
Еще оптимизировать, или достаточно? Там еще несколько узких мест есть, но не столь критических.
Спасибо! Hotspot в выделении n раз O(n) памяти значит. Буду внимательнее в следующий раз.
За
ios_base::sync_with_stdio(0);тоже спасибо.ios_base::sync_with_stdio(0);А что это значит?Гугл в помощь:)
Можете почитать вот это: Знаете ли вы что?
I suspect that the above code block is the problem. The code initializes the "flag" vector of size 2*n at each loop iteration, and there are O(n) loops. The runtime is O(n^2), which shouldn't fit the time limit (I'm actually very surprised it worked).
I made a few modifications to your algorithm (such that you can use just one flag array without reinitialization): check it out 3346847.
Thank you! Hope to be more careful in future.