| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3640 |
| 2 | Benq | 3593 |
| 3 | tourist | 3572 |
| 4 | orzdevinwang | 3561 |
| 5 | cnnfls_csy | 3539 |
| 6 | ecnerwala | 3534 |
| 7 | Radewoosh | 3532 |
| 8 | gyh20 | 3447 |
| 9 | Rebelz | 3409 |
| 10 | Geothermal | 3408 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
Why does this code get accepted 55539853 and this does not 55539543?
I believe the time complexity of 1st submission is O(k(n+m)) for k bfs and then O(nklog(k)) for sorting each node.
Can someone tell the complexity of the second code because of which it is failing.
For getting s smallest element I am using slog(s) complexity in bfs in 2nd submission.
your accepted solutions runs in 1.7 second, which is close to the time limit, so sort vector is faster than popping from priority queue one by one, and therefore you get TLE?
Also, please learn to ask question instead of just posting codes. You can say like: solution 1 uses priority_queue and popping one by one while solution uses vector and sorting it. This will reduce the time taken for people to help you and therefore it will be more likely for someone to help.
But ain't it the same thing. Sorting n elements O(nlog(n)) Popping priority queue O(log(n)) for 1 element so O(nlog(n)) for n elements??
Yes, it is the same in terms of time complexity. But having the same time complexity does not imply that the code is equally fast. For instance, sorting the code 1 time is O(nlog(n)), but sorting it twice is also O(nlog(n)), but is the performance of both code going to be the same?