BiNarY_OVerFloW's blog

By BiNarY_OVerFloW, history, 6 weeks ago, In English

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|

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Try initializing the vectors globally (outside of main())

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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;.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.