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.
Auto comment: topic has been updated by minhi1 (previous revision, new revision, compare).
Do you simply want the colors of the nodes after all $$$q$$$ queries? Or find the color of some node after each query.
Oh I mean after all queries.
where can I find this question?
Ah just a training problem in my school
I think a possible solution may be as follows:
One can convert a operation of "color all nodes with the smallest distance to $$$u$$$ less than or equal to $$$d$$$" to "color all nodes with the smallest distance to $$$v$$$ less than or equal to $$$d-1$$$" for $$$v=u$$$ and all $$$v$$$ adjacent to $$$u$$$. And for all operations with the same $$$u$$$ and $$$d$$$, we only need to consider the last one.
Thus if we take all operations offline, we can convert the problem with $$$d\leq D$$$ to the problem with $$$d\leq D-1$$$ in $$$O(n+m)$$$ time using the statement above, resulting in a $$$O((n+m)\max d)$$$ solution.
omg thank you so much. At first I did the same but still got TLE, fixed it thanks to your idea "only needs latest (u,d)".