ToErr's blog

By ToErr, history, 4 weeks ago, In English,

this submission using priority_queue is giving TLE :

where using set giving AC :

problem link:

could anyone point me out what is wrong here! i am literally not getting the point :(

  • Vote: I like it  
  • -15
  • Vote: I do not like it  

4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

I think you need to check whether not-unique items being inserting into container or not.

set keeps only unique items. priorityqueue doesn't. Therefore you can execute for-loop inside while-loop too many extra times and get TLE.

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

    yes, thank you for pointing it out.

    it is giving time limit for this 'non-unique' pushing.

    if the edges are like:







    then x will be pushed n times in the queue,which will lead the complexity to O(n^2).

    it is sad that i have missed the point.

    again thank you for pointing this.