Vector push_backs занимают много времени (нужна оптимизация)

Revision ru3, by polosatic, 2024-08-29 13:05:01

Недавно я решал эту задачу. Очевидно, тут нужны компоненты сильной связности. Я их написал и получил TL14: 277474774.

Я знал, что пушбэки в 1e6 веторов очень медленные из-за динамической реаллокации. Я также знал единственный способ исправить это: предподсчитать размер каждого вектора, и интерепретировать vector<vector> как один статический массив. Реализовывать это было неприятно, но я справился и получил TL38: 277476691

Я пытался добавить разные оптимизации: убирал последний вектор Эйлерова обхода, добавлял прагмы, но решение не проходило 38 тест. Поэтому, у меня возникло 2 вопроса для самых опытных оптимизаторов:

  1. Есть ли другой, более простой способ ускорить пушбэки в векторы, без предподсчета размера каждого вектора?

  2. Почему мое решение падает по TL и как его ускорить? Ограничения до $$$10^6$$$ должны влезать в 2.5 секунды.

UPD: #define vector basic_string — очень хорошая оптимизация.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru6 Russian polosatic 2024-08-29 13:33:55 109
en6 English polosatic 2024-08-29 13:32:23 103
ru5 Russian polosatic 2024-08-29 13:12:24 1 Мелкая правка: 'и в 1e6 веторов очен' -> 'и в 1e6 векторов очен'
ru4 Russian polosatic 2024-08-29 13:10:32 96
en5 English polosatic 2024-08-29 13:09:47 103
ru3 Russian polosatic 2024-08-29 13:05:01 138
en4 English polosatic 2024-08-29 13:03:50 61
en3 English polosatic 2024-08-29 13:01:59 68
en2 English polosatic 2024-08-29 08:09:26 44 Tiny change: 'ion get TL? Constrai' -> 'ion get TL, and how to speed up it? Constrai'
ru2 Russian polosatic 2024-08-29 08:08:37 1279
en1 English polosatic 2024-08-29 08:01:43 902 Initial revision for English translation
ru1 Russian polosatic 2024-08-29 08:01:04 902 Первая редакция (опубликовано)