Overview

This problem asks you to organize the monetary transactions between the person who paid and the people who used each expense during a trip, and determine the final amount each person should receive (or pay).

Analysis

What we want to know for each person is the difference \(D_j\), which is “total amount actually paid upfront” minus “total amount they should have borne.”

Let’s consider a concrete example. In a group of 3 people, suppose person 1 paid 900 yen upfront, and the users were person 1, person 2, and person 3.

• Person 1 paid 900 yen upfront → add \(+900\) to \(D_1\)
• The cost per person is \(900 \div 3 = 300\) yen
• Subtract \(300\) from \(D\) for each of person 1, person 2, and person 3

Result: \(D_1 = 900 - 300 = 600\), \(D_2 = -300\), \(D_3 = -300\)

This means person 1 should receive 600 yen, and person 2 and person 3 should each pay 300 yen.

Thus, for each payment, we just need to perform the following two operations:

1. Add \(C_i\) to \(D\) for the person \(P_i\) who paid upfront
2. Subtract the share \(\frac{C_i}{K_i}\) from \(D\) for each user \(B_{i,k}\)

Even if we naively iterate over all payments and all users, the constraint guarantees \(\sum_{i=1}^{M} K_i \leq 10^5\), so the total number of user iterations is at most \(10^5\). A straightforward implementation without any special tricks runs sufficiently fast.

Algorithm

1. Initialize an array \(D\) of length \(N+1\) with \(0\) (using 1-indexed).
2. For each payment \(i = 1, 2, \ldots, M\):
   • Add \(C_i\) to \(D[P_i]\) for the person \(P_i\) who paid upfront.
   • Compute the per-person share \(\text{share} = C_i \div K_i\).
   • For each person \(b\) in the user list \(B_{i,1}, \ldots, B_{i,K_i}\), subtract \(\text{share}\) from \(D[b]\).
3. Output \(D[j]\) for \(j = 1, 2, \ldots, N\) in order.

Complexity

• Time complexity: \(O(N + \sum_{i=1}^{M} K_i)\)
  • Processing each payment takes \(O(1)\) for adding to the payer and \(O(K_i)\) for subtracting from the users, totaling \(O(\sum K_i)\). Output takes \(O(N)\).
• Space complexity: \(O(N + \sum_{i=1}^{M} K_i)\)
  • \(O(N)\) for the array \(D\), and \(O(\max K_i)\) for reading input (since we process each line individually).

Implementation Notes

• Fast input: In Python, using sys.stdin.readline allows faster input reading. This is effective when \(M\) or \(K_i\) is large.

• Handling input given on a single line: Each payment line contains \(P_i, C_i, K_i\) followed by \(K_i\) user numbers. It is concise to read them all at once with list(map(int, input().split())) and split using slicing.

• Integer division: Since \(\frac{C_i}{K_i}\) is guaranteed to be an integer, it can be safely computed with C // K in Python.

• When the payer is included among the users: There are cases where the person who paid upfront is also a user. In that case, both addition and subtraction are applied, but no special case handling is needed — the computation is correct as-is.

  Source Code

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    D = [0] * (N + 1)
    for _ in range(M):
        parts = list(map(int, input().split()))
        P = parts[0]
        C = parts[1]
        K = parts[2]
        B = parts[3:3 + K]
        D[P] += C
        share = C // K
        for b in B:
            D[b] -= share
    for j in range(1, N + 1):
        print(D[j])

main()

This editorial was generated by claude4.6opus-thinking.