Overview

This problem asks you to process each location in order of decreasing elevation, simulate how water flows from higher to lower points, and determine the final water volume at each location.

Analysis

The key property of this problem is that water only flows “from higher elevation points to lower elevation points.” This allows us to treat waterways as “one-way paths (directed edges) from higher elevation points to lower elevation points.” Waterways connecting points at the same elevation can be ignored since no water flows through them.

If we were to perform a naive simulation that gradually moves water over time, we would need to update the state every time water flows, resulting in enormous computation time (causing TLE).

However, what happens if we process locations in “decreasing order of elevation”? When processing a location \(v\), all locations with higher elevation than \(v\) have already been processed. In other words, no new water will ever flow into \(v\) after this point. Therefore, at the time we process \(v\), its water volume is completely determined, and we only need to distribute its water downstream once to complete the processing for \(v\). This is the same concept as “topological sorting of a Directed Acyclic Graph (DAG)” in graph theory.

Algorithm

1. Graph Construction: For each waterway, compare the elevations of the two connected locations. Create a directed edge from the higher elevation point to the lower elevation point and build an adjacency list (adj). If the elevations are the same, do not create an edge.
2. Recording Dams: Record the information about which locations have dams installed using a boolean array (is_dam) or similar structure.
3. Determining Processing Order: Sort the location numbers \(1 \dots N\) in decreasing order of elevation \(H\) (highest first).
4. Flow Simulation: Process each location \(u\) in the sorted order and perform the following:
   • If \(u\) has a dam installed: Water does not flow out, so do nothing.
   • If \(u\) has no dam and has \(d\) downstream adjacent locations (destinations of directed edges) where \(d \geq 1\): Divide the water volume \(W_u\) equally into \(d\) parts and add each part to the water volume of the corresponding downstream adjacent location. Then set \(W_u\) to \(0\).
   • If \(u\) has no dam and has no downstream adjacent locations: Water does not flow out, so do nothing.
5. Output Results: Output the water volume at each location after all processing is complete.

Complexity

• Time Complexity: \(O(N \log N + M)\) Sorting the locations takes \(O(N \log N)\) time. Graph construction and flow simulation examine each location and each waterway (edge) only once, completing in \(O(N + M)\) time. Overall, this is \(O(N \log N + M)\), which is sufficiently fast under the given constraints.
• Space Complexity: \(O(N + M)\) Used to store the elevation and water volume arrays, as well as the graph’s adjacency list.

Implementation Notes

• Handling Floating-Point Numbers: Since water volumes become fractional due to equal distribution, calculations should use floating-point numbers (such as float). When outputting, it is safe to ensure a sufficient number of decimal places to prevent incorrect answers due to precision errors (e.g., f"{w:.9f}" in Python).

• Fast I/O: Since the input data size (\(N, M\)) can be as large as \(2 \times 10^5\), in some languages like Python, reading all input at once (e.g., sys.stdin.read().split()) can help reduce execution time.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    H = [int(x) for x in input_data[3:N+3]]
    W = [float(x) for x in input_data[N+3:2*N+3]]
    
    idx = 2 * N + 3
    
    adj = [[] for _ in range(N)]
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        idx += 2
        
        if H[u] > H[v]:
            adj[u].append(v)
        elif H[v] > H[u]:
            adj[v].append(u)
            
    is_dam = [False] * N
    if K > 0:
        for _ in range(K):
            s = int(input_data[idx]) - 1
            is_dam[s] = True
            idx += 1
            
    order = sorted(range(N), key=lambda x: H[x], reverse=True)
    
    for u in order:
        if is_dam[u]:
            continue
        d = len(adj[u])
        if d > 0:
            flow = W[u] / d
            for v in adj[u]:
                W[v] += flow
            W[u] = 0.0
            
    print(*(f"{w:.9f}" for w in W))

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.