概要

標高の高い地点から低い地点へだけ水が流れるという規則のもとで、ダムの有無も考慮しつつ、最終的に各地点に残る水量をシミュレーションする問題です。

考察

重要な観察は次の2点です。

• 水は必ず「高い → 低い」へしか流れない（同じ標高間は流れない）
  したがって、水の移動は標高に関して循環せず、標高の降順で処理すれば「その地点に流れ込む可能性がある水」はすべて既に集まった状態になります。

• 問題文が指定する処理順（標高の高い順）通りに1回ずつ処理すればよい
  各地点は、自分が処理される時点の水 \(w\) を（ダムでなければ）下流隣接地点へ均等分配して \(0\) になります。
  これはまさに「上から順に確定させる」形なので、反復して収束させるようなシミュレーション（毎回少しずつ流す、など）は不要です。

素朴に「水が流れなくなるまで繰り返す」ような実装をすると、最悪の場合に何度も辺をなめることになり \(O(NM)\) のように膨れ、TLE の原因になります。
本問は 各地点を1度だけ処理し、各辺（正確には高→低の向きにした辺）も高々1度だけ使えば十分です。

アルゴリズム

1. 有向グラフ（高→低）を作る
   各水路 \((u, v)\) について、
   • \(H_u > H_v\) なら \(u \to v\) を「下流」辺として登録
   • \(H_v > H_u\) なら \(v \to u\) を登録
   • \(H_u = H_v\) なら何も登録（流れない）

こうして各地点 \(i\) について「下流隣接地点のリスト」down[i] を持ちます。

1. ダム設置地点を dam[i] で管理
   ダムがある地点は「流出しない」ので、処理時にスキップします。

2. 地点を標高の降順にソートして順に処理
   order を \(H\) の降順に並べ、順に地点 \(v\) を処理します。

   • もし dam[v] == True なら何もしない（その場に残る）
   • そうでなく、下流隣接地点が \(d \ge 1\) 個あるなら
     現在の水量 \(w\) を \(d\) 等分して各下流へ加算：各下流に \(\frac{w}{d}\) を足す
     最後に water[v] = 0
   • 下流隣接地点がないなら水は残る（何もしない）

標高降順で処理するため、たとえば \(A \to B \to C\) のように流れる場合でも、 - \(A\) を処理すると \(B\) に水が加算される - 次に \(B\) を処理する時点ではその水が既に water[B] に含まれている
という形で、問題文の「即座に蓄積され、まとめて扱われる」を自然に再現できます。

計算量

• 時間計算量: \(O(N \log N + M)\)
  （標高でのソートが \(O(N \log N)\)、辺の向き付けと分配が合計 \(O(M)\)）
• 空間計算量: \(O(N + M)\)
  （下流リストと各種配列）

実装のポイント

• 同標高の扱い：\(H_u = H_v\) の辺は「流れない」ので、下流リストに入れないこと。

• 浮動小数の使用：分配で \(\frac{w}{d}\) が小数になり得るため、water は float で持つ（出力も誤差許容）。

• 高速入力：\(N, M \le 2 \times 10^5\) なので、sys.stdin.buffer.read() でまとめて読む実装が安全。

• 無駄な計算の回避：water[v] == 0 のときは分配処理をスキップすると少し高速化できます。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。