Overview

This problem asks us to distribute water as evenly as possible within each group (connected component) of reservoirs connected by channels, and minimize the difference between the overall “maximum water volume” and “minimum water volume.”

Analysis

1. Consider each connected component independently

Channels connect reservoirs bidirectionally. A collection of reservoirs that are directly or indirectly connected through channels is called a connected component. Since water cannot be transferred between different connected components, we consider distributing water independently for each connected component.

2. Optimal distribution within a connected component

For a connected component \(C\), let \(S_C\) be the number of reservoirs and \(W_C\) be the total amount of water. To minimize the difference between the maximum and minimum water volumes within this connected component, distributing water as evenly as possible is optimal.

When distributing \(W_C\) liters of water as evenly as possible among \(S_C\) reservoirs, each reservoir’s water volume becomes one of the following: - \(\lfloor W_C / S_C \rfloor\) (floor division) - \(\lceil W_C / S_C \rceil\) (ceiling division)

For example, if the total water is \(10\) liters and there are \(3\) reservoirs, the distribution becomes \((3, 3, 4)\), with a minimum of \(3\) and maximum of \(4\).

3. Regarding the constraint “water volume must always be at least 1 liter”

The problem states that “immediately after any operation, the water volume of every reservoir must be at least \(1\) liter.” Since each reservoir initially has at least \(1\) liter of water, the total water \(W_C\) for each connected component is guaranteed to be at least the number of reservoirs \(S_C\) (\(W_C \geq S_C\)). Therefore, the minimum value \(\lfloor W_C / S_C \rfloor\) when distributing evenly is always at least \(1\), and we can transition to this optimal distribution state without any reservoir’s water volume ever reaching \(0\).

4. Overall minimum and maximum values

When water is distributed evenly within each connected component: - The overall minimum water volume among all reservoirs is the minimum of the minimum values across all connected components, i.e., \(\min_{C} \lfloor W_C / S_C \rfloor\). - The overall maximum water volume among all reservoirs is the maximum of the maximum values across all connected components, i.e., \(\max_{C} \lceil W_C / S_C \rceil\).

Therefore, the minimum difference we seek is \((\text{overall maximum}) - (\text{overall minimum})\).

Algorithm

1. Classifying connected components: Use Union-Find (disjoint set data structure) to group reservoirs connected by channels.
2. Aggregating information: For each connected component, calculate the number of reservoirs (size) \(S_C\) and the total initial water volume \(W_C\).
3. Computing maximum and minimum: For each connected component \(C\), compute:
   • Minimum value \(L_C = \lfloor W_C / S_C \rfloor\)
   • Maximum value \(R_C = \lceil W_C / S_C \rceil\)

Then find the minimum of \(L_C\) across all connected components (min_L) and the maximum of \(R_C\) across all connected components (max_R). 4. Output the answer: Output max_R - min_L.

Complexity

• Time complexity: \(O(N + M \alpha(N))\)
  • Building connected components using Union-Find takes \(O(M \alpha(N))\) (\(\alpha\) is the inverse Ackermann function, which is practically constant).
  • Traversing the parent of each reservoir to aggregate sizes and sums takes \(O(N \alpha(N))\).
  • This runs sufficiently fast for the constraints \(N, M \leq 2 \times 10^5\).
• Space complexity: \(O(N)\)
  • The Union-Find arrays and the arrays storing each connected component’s size and sum use \(O(N)\) memory.

Implementation Notes

• Integer ceiling division: When computing the ceiling division \(\lceil W_C / S_C \rceil\) in a program, using floating-point numbers (float) may introduce errors. To compute this exactly using only integer types, the following technique is used: $\(\lceil W_C / S_C \rceil = (W_C + S_C - 1) // S_C\)$

• Path compression in Union-Find: By performing “path compression” in the find function—reconnecting each node directly to the root—the tree height is kept low and queries are sped up.

  Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    M = int(data[1])

    P = [0] + [int(x) for x in data[2 : 2 + N]]

    parent = list(range(N + 1))

    def find(i):
        path = []
        while parent[i] != i:
            path.append(i)
            i = parent[i]
        for node in path:
            parent[node] = i
        return i

    def union(i, j):
        root_i = find(i)
        root_j = find(j)
        if root_i != root_j:
            parent[root_i] = root_j

    idx = 2 + N
    for _ in range(M):
        u = int(data[idx])
        v = int(data[idx + 1])
        union(u, v)
        idx += 2

    sizes = [0] * (N + 1)
    sums = [0] * (N + 1)

    for i in range(1, N + 1):
        root = find(i)
        sizes[root] += 1
        sums[root] += P[i]

    min_L = float("inf")
    max_R = -float("inf")

    for i in range(1, N + 1):
        if sizes[i] > 0:
            s = sizes[i]
            w = sums[i]
            L = w // s
            R = (w + s - 1) // s
            if L < min_L:
                min_L = L
            if R > max_R:
                max_R = R

    print(max_R - min_L)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.