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

Am I stupid or sth?
Автор Yen_Nhi, история, 2 месяца назад, По-английски

So I tried problem G on the last div3 contest, my solution seems to work with small test case but then gave me an TLE with bigger test case

My submission : https://codeforces.com/contest/1941/submission/251046117

Problem's statement : https://codeforces.com/contest/1941/problem/G

UPD : sorry my dijkstra implementation was wrong :v

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's said that there are $$$2 \cdot 10^5$$$ vertexes, $$$2 \cdot 10^5$$$ edges and also $$$2 \cdot 10^5$$$ colors. Your code's time complexity at least is $$$O(NC)$$$ where $$$C$$$ is the count of colors.

And, priority_queue is not necessary.

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

    I think that the second dimension of the map only contains the color of edges that can go to that vertex

    → Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

No, I am Ac in contest but still TLE in test 47 after hacking 250934676, I think some one had rand a test anti prioryty_queue.

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Yen_Nhi (previous revision, new revision, compare).

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As far as I see from the code, for each pair (vertex v, color c) you traverse all edges incident to v. So basically if there is a vertex with all m edges incident to it and all have different colors, you will do at least O(m^2) operations, which is clear TLE.

→ Ответить