E - Distribute Bunnies Editorial by newsname

Editorial E

Actually, this is a graph theory problem.

For each rabbit, connect the two coordinates it can reach. For example, a rabbit with \(x=4\) and \( r=1\) will have an edge connecting \(3\) and \(5\)

In this way, the problem is transformed into coloring one of the endpoints of each edge and finding the maximum number of colored vertices.

We can analyze each connected component separately:

  • If the connected component is a tree: Arbitrarily select a vertex as the root. Obviously, coloring the endpoint with greater depth for each edge maximizes the answer. Let the number of vertices in this connected component be n; the answer will be \(n−1\).

  • If the connected component is not a tree: Arbitrarily select a spanning tree within the connected component. Then, pick any non-tree edge \((u, v),\) set v as the root of the spanning tree, and color the endpoint with greater depth for each edge in the spanning tree. At this point, vertex v will not be colored, so we can use the non-tree edge \((u, v)\) to color the endpoint \(v\) instead. Let the number of vertices in this connected component be \(n\); the answer from the spanning tree is \(n−1\), and adding the colored vertex v, the final answer becomes \(n\).

The total answer is the sum of the answers of all connected components.

The graph can be stored using a map, and the connected components can be maintained using a disjoint-set union (DSU) (also known as a union-find set).

posted:
last update: