Need help in this problem.
Difference between en2 and en3, changed 0 character(s)
Given a connected graph with n nodes and m edges (n, m <= 1e5). There are q queries (q <= 1e5), each has type of (u, d, c) means to color all nodes which have the smallest distance to u <= d color c (d <= 10, c <= 1e5). What is the color of n nodes after q queries.↵

I can only do smaller subtask when n,m,q <= 2000 with bfs. I do think about solving queries backward and color nodes that are empty but still don't know how to optimize it. Can anyone help me. Thanks.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English minhi1 2024-01-21 13:00:00 0 (published)
en2 English minhi1 2024-01-21 12:53:47 126 (saved to drafts)
en1 English minhi1 2024-01-21 12:53:25 623 Initial revision (published)