Overview

From the information about the songs each member chose, count the number of songs that all \(N\) members commonly selected (songs that appear in everyone’s list).

Analysis

“Songs that all members commonly selected” means that for a given song number \(x\), \(x\) is included in the selection lists of all \(N\) members. Therefore, we can count “how many people selected each song” and finally count the songs where that number equals \(N\).

For example, when \(N=3\), if song 5 is selected by all 3 members, it should be counted, but if only up to 2 members selected it, it is not a common song.

Naively “searching everyone’s list for each song” would result in \(O(NM)\) in the worst case, since the number of songs \(M\) can be up to \(10^5\) and the number of people \(N\) can also be up to \(10^5\), which is far too slow. In this problem, since \(\sum K_i \le 2\times 10^5\) bounds the “total number of selected songs,” we can process efficiently by only counting song numbers that appear in the input.

Algorithm

1. Prepare an array cnt of length \(M\), where cnt[x] represents “the number of people who selected song \(x\)” (initialized to 0).
2. For each member’s input, increment the count with cnt[c] += 1 for each selected song number \(c\).
3. Finally, count and output the number of songs among cnt[1..M] that satisfy cnt[x] == N.

With this method, each song number only needs to be processed as many times as it appears in the input, eliminating the need for expensive searches.

Complexity

• Time complexity: \(O\!\left(\sum_{i=1}^{N} K_i + M\right)\) (Count updates take \(\sum K_i\) operations, and the final aggregation takes \(M\) operations)
• Space complexity: \(O(M)\) (Count array for each song)

Implementation Notes

• Since the input can contain more than \(2\times 10^5\) integers, reading all at once with sys.stdin.buffer.read() is faster.

• Using 1-indexed cnt is clearer: set cnt = [0]*(M+1) and scan cnt[1:].

• The condition for “common to all members” is counting only songs where cnt[x] == N.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    cnt = [0] * (M + 1)
    for _ in range(N):
        k = next(it)
        for _ in range(k):
            c = next(it)
            cnt[c] += 1

    ans = sum(1 for x in cnt[1:] if x == N)
    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.