← 返回题目列表

AtCoder · awc0095_a

A. 结算差旅费用

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

分数: 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