Недавно я решал эту задачу. Очевидно, тут нужны компоненты сильной связности. Я их написал и получил 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: нашел этот блог. Там объяснены нюансы.
If you know beforehand approximately how much space you need, you can probably call std::vector::reserve
Much time ago I have the same issue and tried vector.reserve(), but it also gave me TL. But that time precomputing of all sizes helped my solution to pass.
Well, vectors in general is slower than static array, I'm not very sure about the specifics of it but seems like it's memory allocation mechanics are more complicated
Probably not the most useful idea, however does
emplace_backwork?I tried it when I met this issue in the first time. It also did not work, same as vector.reserve().
Despite the way of constructing an object,
push_backactually has the same implementation asemplace_back.Mushrooms function works in
sqrt(x)/2For the vectors, the fastest way is to use something similar to bucket sort, which is to merge all vectors into one array.
Wow, my bad. I did
k=sqrt(x*2)and got AC.Vectors: 278599566 1625ms
Array: 278600523 921ms
Now I know that there is no other way to speed up push_backs. Thank you.
My vector filled copy paste code for SCCs ACd in around half of the TL, so that probably isn't the cause unless there's some compiler specific wizardry going on. I'm pretty sure the comment above hit the spot: the mushrooms function is the cause.
Use
basic_stringinstead ofvector. They are exactly the same, butbasic_stringis faster. (though the optimization isn't significant)Wow! This is the thing I wanted to know. I added
#define vector basic_stringand it runs in 1186ms instead of 1625! It is 37% faster with just one define! I have never heard it! Before rewriting vector to one array, I will first try this optimization.278616547
UPD: do not use this define if you use
vector<vector<int>> vecinstead ofvector<int> vec[N].27%
1625/1186 = 1.37015177065767284992 1186/1625 = 0.72984615384615384615
Yes, but still 27%, not 37%.
"A is $$$p\%$$$ faster than B" means "the speed of A is $$$p\%$$$ greater than one of B", or, equivalently, $$$v_A = \left(1 + \frac{p}{100}\right)v_B$$$ where $$$v_A$$$ is the speed of A and $$$v_B$$$ is the speed of B. The most natural way to define the speed of a solution is, given it's repeated several times, say that it is equal to its execution frequency, thus $$$v_A = \frac{1}{t_A}$$$ and $$$v_B = \frac{1}{t_B}$$$. So we get $$$\frac{1}{t_A} = \left(1 + \frac{p}{100}\right)\frac{1}{t_B}$$$ and $$$p = \left(\frac{t_B}{t_A} - 1\right) \cdot 100$$$, so $$$p = \frac{1625\text{ ms}}{1186\text{ ms}} \approx 37$$$ is the correct approach.
Taking $$$p = \left(1 - \frac{t_A}{t_B}\right) \cdot 100$$$ does not really make sense here, because, for instance, when we say that A is $$$100\%$$$ faster than B, we mean that A is twice as fast as B rather than that A is momentary.
One can say that $$$1625\text{ ms}$$$ solution is $$$27\%$$$ slower than $$$1186\text{ ms}$$$ solution, it is fine. And if someone says that B is $$$100\%$$$ slower than A, they do mean that A is momentary (or B is infinitely long).
Use this.
I used similar approach in the submission got TL38.
I suggest you also run a profiler on your solution to know exactly what you can optimize. Sometimes things take longer than you expect, even when asymptotics is ok.
I used samply several times, for example.
Наверное дело в самом решении. Я открыл своё старое полное решение, перепослал под c++20 и оно зашло за ~1150ms 278628577. Там и обычные вектора и sqrt, но другой алгос конденсации (через один dfs)
Нашли выше уже, mushrooms работает не за единицу, как должен, оттого и тл. Никаких хитрых оптимизаций не нужно было.
push_backisn't slow,push_backis exactly as fast as intended. Reallocating memory according to your design is slow. You needed to redesign it, which is the standard solution to this problem.Allocation-friendly way to store graphs: https://mirror.codeforces.com/blog/entry/5195
No need for 2d-vectors.
You can check out my submission here, I guess ? 278711068
can you please explain why vector push-back takes more time