Overview

This is a problem where we simulate rainwater accumulated at each point in a mountainous region flowing evenly from higher elevation points to lower elevation points through waterways, and determine the water volume at each point after all processing is complete.

Analysis

Key Observations

1. The processing order is determined by “descending elevation”

Water only flows from higher elevation points to lower elevation points. If we process higher elevation points first, then when processing a point \(v\), all inflow from points higher than \(v\) has already been completed. Since water does not flow between points at the same elevation, the processing order among same-elevation points does not affect the result.

2. Processing each point is a simple distribution operation

When processing point \(v\): - If a dam is installed → do nothing (water is retained) - If there are \(d \geq 1\) downstream adjacent points (neighboring points with strictly lower elevation) → divide the water volume \(w\) equally into \(d\) parts, add each part to the respective downstream point, and set \(v\)’s water volume to \(0\) - If there are no downstream adjacent points → the water remains as is

3. A straightforward simulation is sufficient

Although it may seem complex at first glance, each point is processed exactly once, and each edge is referenced at most twice (once when processing each of its endpoints), so it can be solved with sorting + linear scan. No special data structures are needed.

Concrete Example

If point 1 (elevation 10, water volume 6) has waterways to point 2 (elevation 5) and point 3 (elevation 3), there are 2 downstream adjacent points, so \(6/2 = 3\) liters flow to each point.

Algorithm

1. Read input and construct the adjacency list and dam information.
2. Sort all points in descending order of elevation.
3. Process each point \(v\) in sorted order:
   • If \(v\) has a dam, do nothing.
   • If \(v\)’s current water volume \(w\) is \(0\), do nothing (skip for speedup).
   • Among \(v\)’s adjacent points, enumerate those with elevation strictly less than \(H[v]\), and let \(d\) be their count.
   • If \(d \geq 1\), add \(w/d\) to each downstream adjacent point and set \(W[v] = 0\).
   • If \(d = 0\), the water remains as is.
4. Output the water volume at each point.

Complexity

• Time complexity: \(O(N \log N + N + M)\)
  • \(O(N \log N)\) for sorting
  • Processing each point involves scanning adjacent edges, but overall each edge is referenced at most twice, so \(O(N + M)\)
• Space complexity: \(O(N + M)\)
  • For storing the adjacency list, water volume array, elevation array, etc.

Implementation Notes

• Manage water volumes using floating-point numbers (float): Since equal distribution may result in non-integer water volumes, use float type for calculations.

• Skip points with water volume \(0\): This avoids enumerating downstream adjacent points and provides a constant factor speedup.

• Fast input reading: Since \(N, M\) can be up to \(2 \times 10^5\), using sys.stdin.buffer.read() for bulk reading allows Python to run sufficiently fast.

• When \(K = 0\), the last line does not exist: Add a conditional branch to read dam information only when \(K > 0\).

• Output precision: Since an absolute error within \(10^{-6}\) is required, output with a sufficient number of decimal places such as :.10f.

  Source Code

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    H = [0] * (N + 1)
    for i in range(1, N + 1):
        H[i] = int(input_data[idx]); idx += 1
    
    W = [0.0] * (N + 1)
    for i in range(1, N + 1):
        W[i] = float(input_data[idx]); idx += 1
    
    adj = defaultdict(list)
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)
    
    is_dam = [False] * (N + 1)
    if K > 0:
        for _ in range(K):
            s = int(input_data[idx]); idx += 1
            is_dam[s] = True
    
    # Sort all nodes by height descending
    order = sorted(range(1, N + 1), key=lambda x: -H[x])
    
    for v in order:
        if is_dam[v]:
            continue
        
        w = W[v]
        if w == 0.0:
            continue
        
        # Find downstream neighbors (strictly lower height)
        downstream = []
        for u in adj[v]:
            if H[u] < H[v]:
                downstream.append(u)
        
        d = len(downstream)
        if d == 0:
            continue
        
        # Distribute water equally
        share = w / d
        for u in downstream:
            W[u] += share
        W[v] = 0.0
    
    # Output
    result = []
    for i in range(1, N + 1):
        result.append(f"{W[i]:.10f}")
    print(' '.join(result))

if __name__ == '__main__':
    main()

---

This editorial was generated by claude4.6opus-thinking.