Недавно я решал эту задачу. Очевидно, тут нужны компоненты сильной связности. Я их написал и получил TL14: 277474774.
Я знал, что пушбэки в 1e6 векторов очень медленные из-за динамической реаллокации. Я также знал единственный способ исправить это: предподсчитать размер каждого вектора, и интерепретировать vector<vector> как один статический массив. Реализовывать это было неприятно, но я справился и получил TL38: 277476691
Я пытался добавить разные оптимизации: убирал последний вектор Эйлерова обхода, добавлял прагмы, но решение не проходило 38 тест. Поэтому, у меня возникло 2 вопроса для самых опытных оптимизаторов:
Есть ли другой, более простой способ ускорить пушбэки в векторы, без предподсчета размера каждого вектора?
Почему мое решение падает по TL и как его ускорить? Ограничения до $$$10^6$$$ должны влезать в 2.5 секунды.
UPD: #define vector basic_string — очень хорошая оптимизация. EDIT: не используйте этот define если пользуетесь vector<vector<int>> vec вместо vector<int> vec[N].
UPD2: нашел этот блог. Там объяснены нюансы.
