Vector push_backs take too much time (need optimization)

Правка en5, от polosatic, 2024-08-29 13:09:47

Recenlty I was solving this problem. It was obvious strongly connected components. I wrote them and got TL14: 277474774.

I knew that push_backing to 1e6 vectors is slow due to the dynamic reallocation. I know the only way to handle it: precompute the size of each vector, and reinterpret vector<vector> as a static array. It was awful to implement, but I did it and got TL38: 277476691

Then I tried many things like removing the vector of Euler tour, adding pragmas, but have not passes the test 38. So, there are 2 questions for experienced optimizers:

  1. Is there another, simpler way to speed up vector push_backs, without precomputing each vector's size?

  2. Why does my final solution get TL, and how to speed up it? Constraints up to $$$10^6$$$ are enough to pass in this problem I think.

UPD: #define vector basic_string is a useful optimization.

UPD2: found this blog. There are some explanations.

История

 
 
 
 
Правки
 
 
  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 Первая редакция (опубликовано)