← 返回题目列表

AtCoder · awc0106_b

B. 山区雨水模拟

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥正在对山区进行地形模拟。

山区有 N 位置,每个编号自 1 to N。地点 i 的海拔为 H_i 并且最初成立 W_i 升雨水。

这些位置通过以下方式连接 M 频道。的 j第通道双向连接位置 U_j 和位置 V_j。水只从海拔较高的地方流向海拔较低的地方。也就是说,如果由通道连接的两个位置具有相同的高度,则水不会流过该通道。

对于一个位置 v,在直接连接到的位置中 v 通过通道,海拔严格低于 v 被称为 下游邻居 of v.

高桥已在 K 位置(如果 K = 0,没有安装水坝)。大坝安装的位置都有编号 S_1, S_2, \ldots, S_K。在建有水坝的地方,水可以从其他地方通过渠道流入,但水不会从该地方流出。

各地点的出水按以下程序处理:

  1. 按海拔降序对所有位置进行排序。由于水不会在相同高程的位置之间流动,因此具有相同高程的位置之间的排序是任意的(结果不取决于处理顺序)。
  2. 按此顺序一一处理每个位置。让 v 是正在处理的位置,并让 w 升 是当前累积的水量 v.
  • 如果大坝安装在 v:什么都不做。全部 w 升水仍处于 v.
  • 如果没有安装大坝 v,并且有 d 下游邻居(d \geq 1):全部 w 升水 v 流出。流出的水平均分配给 d 下游邻居,每个下游邻居接收 \frac{w}{d} 升水(即使下游邻居安装了水坝,水也会流入)。出水后水量为 v 变为 0.
  • 如果没有安装大坝 v,并且没有下游邻居 (包括没有连接通道的孤立位置,或者所有连接位置的标高都大于或等于 v): 水保持在 v 原样。

当水在某个位置的流出处理期间流入下游邻居时,该水立即聚集在下游邻居处,并在该下游邻居本身被处理时被集中处理。

所有流出处理完成后,确定每个位置的剩余水量。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq N
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq W_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
  • 最多有一个通道连接同一对位置(无多边)
  • 1 \leq S_k \leq N (1 \leq k \leq K)
  • S_1, S_2, \ldots, S_K 都是不同的
  • 所有输入值均为整数

输入

N M K
H_1 H_2 \ldots H_N
W_1 W_2 \ldots W_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
S_1 S_2 \ldots S_K
  • 第一行包含位置数 N,通道数 M,以及有水坝的地点数量 K,以空格分隔。
  • 第二行包含标高 每个位置的 H_1, H_2, \ldots, H_N ,以空格分隔。
  • 第三行包含初始水量 W_1, W_2, \ldots, W_N ,以空格分隔。
  • 以下 M 行包含频道信息。的 j- 这些行(行 整个输入的 3 + j 包含位置 U_j 和 V_j 由 j第一个通道,以空格分隔。
  • If K \geq 1,最后一行包含位置编号 S_1, S_2, \ldots, S_K 安装水坝的地方,以空格分隔。如果 K = 0,该行不存在。

输出

输出所有流出处理完成后每个位置的水量,从位置 1 到位置 N,单行上用空格分隔。由于平均分配可能会导致非整数水量,因此小数输出是可以接受的。对于每个输出值,如果与真实值的绝对误差最多为 10^{-6},或者如果真值非零且相对误差至多 10^{-6}.


示例输入 1

4 4 0
10 20 5 5
0 12 0 0
1 2
1 3
2 3
2 4

示例输出 1

0.0000000000 0.0000000000 8.0000000000 4.0000000000

示例输入 2

3 2 1
30 20 10
6 0 0
1 2
2 3
2

示例输出 2

0.0000000000 6.0000000000 0.0000000000

示例输入 3

6 7 1
50 40 40 30 20 10
18 6 0 0 0 0
1 2
1 3
2 4
2 5
3 5
4 6
5 6
5

示例输出 3

0.0000000000 0.0000000000 0.0000000000 0.0000000000 16.5000000000 7.5000000000

示例输入 4

8 10 2
100 80 80 60 50 50 30 10
24 0 0 0 12 0 0 0
1 2
1 3
2 4
3 4
3 5
4 6
4 7
5 7
6 8
7 8
4 6

示例输出 4

0.0000000000 0.0000000000 0.0000000000 18.0000000000 0.0000000000 0.0000000000 0.0000000000 18.0000000000

示例输入 5

1 0 0
1000000000
999999999

示例输出 5

999999999.0000000000