分数: 266 分
问题陈述
一组 N 人们去旅行了。成员编号为 1 to N。旅行期间产生的费用由其中一名成员代表其他成员预先支付。旅行结束后,他们决定公平地解决大家的所有费用。
共 M 付款是在旅行期间支付的。对于 i第次付款 (1 \leq i \leq M), 人 P_i 已付款 C_i 日元预付。这笔付款是为了 使用过的 K_i 会员,用户是 B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}。那个人 P_i 预付款的人可能会或可能不会包含在用户中。对于每笔付款,费用由各方平均分摊 K_i 用户。即每个用户应承担的金额为 \frac{C_i}{K_i} 日元。
考虑所有付款,定义结算金额 D_j 人 j (1 \leq j \leq N) 如下:
D_j = \sum_{\substack{1 \leq i \leq M \\ P_i = j}} C_i \;-\; \sum_{\substack{1 \leq i \leq M \\ j \in \{B_{i,1}, \ldots, B_{i,K_i}\}}} \frac{C_i}{K_i}
换句话说, D_j 是减去“总金额人 j 应承担“起”人的总金额 j 实际上是预付的。”如果人 j 未预付任何款项,预付总金额为 0 日元。同样,如果人 j 作为用户不包含在任何付款中,他们应承担的总金额为 0 日元。
If D_j 是积极的,人 j 应该收到 D_j 日元。如果 D_j 是否定的,人 j 应该支付 |D_j| 日元。如果 D_j = 0,无需结算。
确定的值 D_j 对于所有人 N 人。请注意,保证每个 \frac{C_i}{K_i} 是一个整数,所以 D_j 也始终是整数。
约束
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq P_i \leq N
- 1 \leq C_i \leq 10^9
- 1 \leq K_i \leq N
- 1 \leq B_{i,1} < B_{i,2} < \ldots < B_{i,K_i} \leq N
- P_i 不一定包含在其中 B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}
- \frac{C_i}{K_i} 是一个整数
- \sum_{i=1}^{M} K_i \leq 10^5
- 所有输入值均为整数
输入
N M
P_1 C_1 K_1 B_{1,1} B_{1,2} \ldots B_{1,K_1}
P_2 C_2 K_2 B_{2,1} B_{2,2} \ldots B_{2,K_2}
\vdots
P_M C_M K_M B_{M,1} B_{M,2} \ldots B_{M,K_M}
- 第一行包含群组人数 N 和付款次数 M,用空格分隔。
- 以下 M 行提供每笔付款的信息。
- 的 i- 第这些行 (1 \leq i \leq M) 包含,对于 i-第付款,预付款人的数量 P_i,金额 C_i,用户数 K_i,以及用户号码 B_{i,1}, B_{i,2}, \ldots, B_{i,K_i},用空格分隔。
输出
输出 N 行。上 j第行 (1 \leq j \leq N),输出结算金额 D_j 人 j 作为整数。如果 D_j 为负,带负号输出。如果 D_j = 0,输出 0.
示例输入 1
3 2 1 6000 3 1 2 3 2 4000 2 2 3
示例输出 1
4000 0 -4000
示例输入 2
5 4 1 10000 5 1 2 3 4 5 3 6000 3 1 2 3 2 8000 2 2 4 5 3000 3 3 4 5
示例输出 2
6000 0 1000 -7000 0
示例输入 3
6 5 1 12000 6 1 2 3 4 5 6 2 9000 3 1 2 3 4 8000 4 1 4 5 6 6 5000 2 2 6 3 7000 2 3 5
示例输出 3
5000 1500 -1500 4000 -7500 -1500