Need help in this problem.

Revision en3, by minhi1, 2024-01-21 13:00:00

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.

Tags graph

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)