https://codeforces.com/contest/20/submission/105231894
I am Implementing the soln above But i am getting MLE(it is totally unexpected) I can not figure out when i see others code of same problem they have done exactly same thing and they get AC but i am getting MLE https://codeforces.com/contest/20/submission/105228166(watch this) please help|
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.04.2024 11:07:43 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
Try initializing the vectors globally (outside of main())
Thanks Bro! When I declare it globally it shows WA now i will fix it Bro Can you explain the reason why declaring it globally not locally
I don't really know much about it, but it's related to memory allocation in C++. I hope this comment explains it better
I made some changes to your code and it was Accepted.
Link https://codeforces.com/contest/20/submission/105237381
First, the default priority queue is max-heap in C++, but in Dijkstra's algorithm, we want min-heap, so you need to declare as in my submission.
Secondly, you should skip processing the current node if the distance currently in the heap is not the best distance. By adding this line
if (b.first > d[b.second]) continue;.vector<vector<pair<long long int, long long int>>>k(200005,(vector<pair<long long int,long long int>>(200005)));(declared in global scope) when i try to declare vector in this way program doesn't run(it just freezes)
when i use this it works(perfectly) vector<long long int,long long int>>k[200005](declared in global scope)
what is difference between these two?
The way you are declaring tries to create space for (200005)^2 pairs, which is a lot(doesn't fit in memory limit).
In the second declaration, you will only add edges that are necessary.