Блог пользователя ToErr

why priority_queue is not behaving as expected?
Автор ToErr, история, 6 лет назад, По-английски

this submission using priority_queue is giving TLE : http://codeforces.me/contest/467/submission/43003735

where using set giving AC : http://codeforces.me/contest/467/submission/43003953

problem link: http://codeforces.me/contest/467/problem/D

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

  • Проголосовать: нравится
  • -15
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    yes, thank you for pointing it out.

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

    if the edges are like:

    1-x

    2-x

    ...

    ...

    ...

    n-x

    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.

    → Ответить