minhi1's blog

By minhi1, history, 10 months ago, In English

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

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

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

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

Do you simply want the colors of the nodes after all $$$q$$$ queries? Or find the color of some node after each query.

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

where can I find this question?

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

    Ah just a training problem in my school

»
10 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

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

    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)".