Overview

This problem involves calculating the final balance (amount to receive or amount to pay) for each individual, given multiple payments (advances) made during a trip.

Analysis

For each payment, the following two factors affect the balance: 1. Plus for the person who advanced the payment: Since they paid the full amount \(C_i\), their balance increases by that amount. 2. Minus for the users: The \(K_i\) people who used the service each bear an equal share of \(\frac{C_i}{K_i}\), so their balance decreases by that amount.

The key point of this problem is whether simulating how much each person gained or lost one by one is fast enough. Looking at the constraints, the number of people \(N\) and the number of payments \(M\) are at most \(10^5\). Additionally, the total number of users across all payments \(\sum K_i\) is also at most \(10^5\). Therefore, even if we naively “add to the person who advanced the payment” and “subtract from all users” for each payment, the total number of operations is approximately \(M + \sum K_i\) (about \(2 \times 10^5\)), which is well within the time limit.

Algorithm

1. Prepare an array (or list) \(D\) of length \(N+1\), initialized to all \(0\)s. \(D[j]\) represents the current balance of person \(j\).
2. For each payment \(i = 1, 2, \ldots, M\), perform the following:
   • Update the balance of the person \(P_i\) who advanced the payment: \(D[P_i] \leftarrow D[P_i] + C_i\)
   • Calculate the per-person share: \(share = \frac{C_i}{K_i}\)
   • For each user \(B_{i,j}\) (\(j=1 \ldots K_i\)), update the balance: \(D[B_{i,j}] \leftarrow D[B_{i,j}] - share\)
3. After processing all payments, output the values from \(D[1]\) to \(D[N]\) in order.

Complexity

• Time complexity: \(O(N + M + \sum K_i)\)
  • Array initialization takes \(O(N)\), and processing each payment takes \(O(1 + K_i)\), so the overall complexity is linear with respect to the input size.
• Space complexity: \(O(N)\)
  • The size of the array \(D\) for storing each person’s balance is proportional to \(N\).

Implementation Notes

• Fast I/O: Since the number of input data can reach up to hundreds of thousands, repeatedly using Python’s standard input() may result in long execution times. It is more efficient to read all input at once using sys.stdin.read().split() and sequentially extract values from the list.

• Integer handling: Since the problem guarantees that \(\frac{C_i}{K_i}\) is an integer, using floor division // to compute in integers avoids floating-point precision errors.

• Output optimization: Rather than calling print() for each of the \(N\) lines, it is faster to convert the results to a list of strings and output them all at once using '\n'.join().

  Source Code

import sys

def main():
    # 旅行の立て替え精算の問題を解くためのメイン関数
    # sys.stdin.read().split() を使用して、入力を一括で取得しトークンに分割します
    # これにより、大量の入力データに対しても高速に処理することが可能です
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了します
    if not input_data:
        return
    
    # グループの人数 N と支払い回数 M を取得
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各人の精算バランスを格納するリスト D
    # D[j] は人 j の「実際に立て替えた合計金額」から「本来負担すべき合計金額」を引いた値
    # 人の番号は 1 から N であるため、サイズ N+1 のリストを用意します
    D = [0] * (N + 1)
    
    # 現在処理しているトークンのインデックス
    ptr = 2
    
    # M 回の支払い情報を順に処理
    for _ in range(M):
        # 立て替えた人の番号 P_i, 金額 C_i, 利用者数 K_i を取得
        p_i = int(input_data[ptr])
        c_i = int(input_data[ptr+1])
        k_i = int(input_data[ptr+2])
        ptr += 3
        
        # 立て替えた人 P_i の実際に支払った金額を加算
        D[p_i] += c_i
        
        # 利用者一人あたりの負担額を計算 (C_i / K_i)
        # 問題の制約により、この値は必ず整数になります
        share = c_i // k_i
        
        # 各利用者の本来負担すべき金額を減算
        # 利用者のリスト B_{i,1}, ..., B_{i,K_i} を順に処理
        for _ in range(k_i):
            b_ij = int(input_data[ptr])
            D[b_ij] -= share
            ptr += 1
            
    # 人 1 から N までの精算バランス D_j を文字列のリストに変換
    results = map(str, D[1:])
    
    # すべての結果を改行区切りで一気に出力
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-thinking.