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

Правка ru6, от polosatic, 2024-08-29 13:33:55

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

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

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

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

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

UPD: #define vector basic_string — очень хорошая оптимизация. EDIT: не используйте этот define если пользуетесь vector<vector<int>> vec вместо vector<int> vec[N].

UPD2: нашел этот блог. Там объяснены нюансы.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru6 Русский polosatic 2024-08-29 13:33:55 109
en6 Английский polosatic 2024-08-29 13:32:23 103
ru5 Русский polosatic 2024-08-29 13:12:24 1 Мелкая правка: 'и в 1e6 веторов очен' -> 'и в 1e6 векторов очен'
ru4 Русский polosatic 2024-08-29 13:10:32 96
en5 Английский polosatic 2024-08-29 13:09:47 103
ru3 Русский polosatic 2024-08-29 13:05:01 138
en4 Английский polosatic 2024-08-29 13:03:50 61
en3 Английский polosatic 2024-08-29 13:01:59 68
en2 Английский 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 Русский polosatic 2024-08-29 08:08:37 1279
en1 Английский polosatic 2024-08-29 08:01:43 902 Initial revision for English translation
ru1 Русский polosatic 2024-08-29 08:01:04 902 Первая редакция (опубликовано)