Overview

This is a problem where you simulate the final amount of water remaining at each point, considering the rule that water flows only from higher elevation points to lower elevation points, while also accounting for the presence or absence of dams.

Key Observations

The two important observations are:

• Water only flows from “high → low” (it does not flow between points of the same elevation)
  Therefore, water movement does not cycle with respect to elevation, and if we process in descending order of elevation, all water that could potentially flow into a given point has already been accumulated.

• We only need to process each point once, in the order specified by the problem (from highest elevation to lowest)
  At each point, when it is processed, its water \(w\) is evenly distributed to downstream adjacent points (unless it is a dam), and its water becomes \(0\).
  This is exactly a “settle from the top down” approach, so iterative simulation until convergence (e.g., flowing a little at a time) is unnecessary.

A naive implementation that “repeats until water stops flowing” could end up traversing edges many times in the worst case, ballooning to \(O(NM)\) and causing TLE.
In this problem, processing each point only once and using each edge (specifically, each edge directed from high to low) at most once is sufficient.

Algorithm

1. Build a directed graph (high → low)
   For each waterway \((u, v)\):
   • If \(H_u > H_v\), register \(u \to v\) as a “downstream” edge
   • If \(H_v > H_u\), register \(v \to u\)
   • If \(H_u = H_v\), register nothing (no flow)

This gives us a “list of downstream adjacent points” down[i] for each point \(i\).

1. Manage dam locations with dam[i]
   Points with dams “do not release water”, so they are skipped during processing.

2. Sort points in descending order of elevation and process them in order
   Sort order in descending order of \(H\), and process each point \(v\) in order:

   • If dam[v] == True, do nothing (water stays there)
   • Otherwise, if there are \(d \ge 1\) downstream adjacent points,
     divide the current water amount \(w\) equally among \(d\) downstream points: add \(\frac{w}{d}\) to each downstream point
     Then set water[v] = 0
   • If there are no downstream adjacent points, the water remains (do nothing)

Because we process in descending order of elevation, even in a case where water flows like \(A \to B \to C\): - When \(A\) is processed, water is added to \(B\) - When \(B\) is processed next, that water is already included in water[B]
This naturally reproduces the problem’s specification that water “accumulates immediately and is handled collectively.”

Complexity

• Time complexity: \(O(N \log N + M)\)
  (Sorting by elevation is \(O(N \log N)\), directing edges and distributing water is \(O(M)\) in total)
• Space complexity: \(O(N + M)\)
  (Downstream lists and various arrays)

Implementation Notes

• Handling equal elevations: Edges where \(H_u = H_v\) mean “no flow”, so do not add them to the downstream list.

• Use of floating point: Since \(\frac{w}{d}\) can be a decimal during distribution, water should be stored as float (output also allows error tolerance).

• Fast input: Since \(N, M \le 2 \times 10^5\), it is safe to use an implementation that reads all at once with sys.stdin.buffer.read().

• Avoiding unnecessary computation: Skipping the distribution process when water[v] == 0 can slightly speed things up.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)
    K = next(it)

    H = [next(it) for _ in range(N)]
    water = [float(next(it)) for _ in range(N)]

    down = [[] for _ in range(N)]
    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        hu = H[u]
        hv = H[v]
        if hu > hv:
            down[u].append(v)
        elif hv > hu:
            down[v].append(u)

    dam = [False] * N
    for _ in range(K):
        s = next(it) - 1
        dam[s] = True

    order = list(range(N))
    order.sort(key=lambda x: H[x], reverse=True)

    for v in order:
        if dam[v]:
            continue
        ds = down[v]
        if not ds:
            continue
        w = water[v]
        if w == 0.0:
            continue
        share = w / len(ds)
        for u in ds:
            water[u] += share
        water[v] = 0.0

    out = ' '.join(f"{w:.10f}" for w in water)
    sys.stdout.write(out + "\n")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.