Overview

Each point in the mountainous region has rainwater, and water flows according to elevation. At points where dams are installed, water does not flow out, while at other points, water is distributed equally to downstream points. We need to find the amount of water remaining at each point in the end.

Analysis

In this problem, we need to simulate water flowing “from higher elevation points to lower elevation points.” The key points are:

• Points must be processed in order from highest to lowest elevation. This is because once water flows, it immediately accumulates at the next point, so processing out of order would cause inconsistencies.
• Water flowing downstream from each point is distributed equally. That is, if there are \(d\) downstream adjacent points, each receives \(1/d\) of the current water amount.
• At points where dams are installed, no water flows out at all. Also, at isolated points or points with no downstream neighbors, the water stays in place.

A naive approach of looking at adjacent points each time and distributing water could be considered, but in the worst case, an extremely large number of water transfers could occur, so an efficient implementation is needed.

In this problem, by pre-sorting points in descending order of elevation and processing them in that order, we can correctly simulate the water flow.

Algorithm

1. Graph Construction
   Build an undirected graph with each point as a node and each waterway as an edge.

2. Computing Downstream Adjacent Points
   For each point \(u\), list the adjacent points \(v\) where \(H_v < H_u\) as “downstream adjacent points.”

3. Sorting by Descending Elevation
   Sort the points in descending order of elevation. This guarantees that water naturally flows from upstream to downstream.

4. Simulating Water Flow
   Process each point in the sorted order:

   • If there is a dam, skip
   • If there are no downstream adjacent points, the water stays
   • If there are downstream adjacent points, distribute the current water amount equally and set the point’s own water amount to 0

5. Output the Result
   Output the final water amount at each point.

Complexity

• Time complexity: \(O(N \log N + M)\)
  
  • Sorting by elevation takes \(O(N \log N)\)
  • Graph construction and computing downstream adjacent points takes \(O(M)\)
  • Water distribution processes each edge at most once, so \(O(M)\)
• Space complexity: \(O(N + M)\)
  
  • Adjacency list, downstream list, water amount array, etc. take \(O(N + M)\)

Implementation Notes

• When elevations are equal, the processing order is arbitrary, and sort stability is not required (it does not affect the result)

• Water amounts should be managed with floating-point numbers (precision is important during distribution)

• Whether a dam exists can be checked efficiently using a set

• Water distribution does not need to be deferred; it can be added immediately during processing (in this implementation, immediate addition is not problematic)

  Source Code

import sys
from collections import defaultdict
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    H = [0] * (N + 1)
    for i in range(1, N + 1):
        H[i] = int(data[idx]); idx += 1
        
    W = [0.0] * (N + 1)
    for i in range(1, N + 1):
        W[i] = float(data[idx]); idx += 1
        
    adj = [[] for _ in range(N + 1)]
    
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)
        
    dams = set()
    if K > 0:
        for _ in range(K):
            s = int(data[idx]); idx += 1
            dams.add(s)
            
    # 各地点の下流隣接地点を計算
    downstream = [[] for _ in range(N + 1)]
    for u in range(1, N + 1):
        for v in adj[u]:
            if H[v] < H[u]:
                downstream[u].append(v)
                
    # 標高の高い順に処理するためのリストを作成
    # 同じ標高の場合は順序は任意で良いので、単純にソート
    nodes = list(range(1, N + 1))
    # 高い順にソート（降順）
    nodes.sort(key=lambda x: H[x], reverse=True)
    
    # 流出処理
    for v in nodes:
        if v in dams:
            continue
        out_deg = len(downstream[v])
        if out_deg == 0:
            continue
        water = W[v]
        if water == 0:
            continue
        distributed = water / out_deg
        for u in downstream[v]:
            W[u] += distributed
        W[v] = 0.0
        
    print(' '.join(f"{W[i]:.10f}" for i in range(1, N + 1)))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.