Yen_Nhi's blog

Am I stupid or sth?
By Yen_Nhi, history, 2 months ago, In English

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

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply