Overview

Given \(N\) members each selecting multiple songs, find the number of songs that all members have selected in common.

Analysis

In this problem, we are given the list of songs each member has selected, and we need to find the intersection of the sets of songs selected by all members.

A naive approach would be to count “how many people selected each song” for every song. However, this requires checking \(N\) people for each of up to \(M\) songs, resulting in a worst-case time complexity of \(O(N \cdot M)\). Given the constraints, this can be up to \(10^{10}\), which cannot be processed within the time limit.

Instead, we consider an efficient approach using “sets.” We start with the set of songs selected by the first member, then iteratively take the intersection with each subsequent member’s set of songs. This way, we ultimately obtain the set of songs selected by all members. This method can be processed efficiently by leveraging the fact that the total size of all song lists is at most \(2 \times 10^5\).

Algorithm

1. Create the set common_songs from the songs selected by the first member.
2. For each subsequent member, create the set songs of songs they selected, and update common_songs by taking its intersection with songs.
3. Output the number of elements in the final common_songs.

By using set operations in this way, we can efficiently find the common elements while avoiding unnecessary comparisons.

Complexity

• Time complexity: \(O(\sum_{i=1}^{N} K_i)\)
  Because we perform set operations proportional to the total number of songs selected by all members.
• Space complexity: \(O(M)\)
  Because we maintain a set that may store up to \(M\) songs.

Implementation Notes

• sys.stdin.read is used for fast input reading.
• The set intersection operation (&=) is used to efficiently update the common part.
• By using the first set as the starting point, the subsequent processing becomes simple.

## Source Code

```python
import sys
from collections import defaultdict

input = sys.stdin.read

data = input().split()
idx = 0

N = int(data[idx])
idx += 1
M = int(data[idx])
idx += 1

# 最初のメンバーの曲リストを取得
k = int(data[idx])
idx += 1
common_songs = set()
for _ in range(k):
    song = int(data[idx])
    idx += 1
    common_songs.add(song)

# 残りのメンバーの曲リストとの共通集合を取る
for i in range(1, N):
    k = int(data[idx])
    idx += 1
    songs = set()
    for _ in range(k):
        song = int(data[idx])
        idx += 1
        songs.add(song)
    common_songs &= songs

print(len(common_songs))

This editorial was generated by qwen3-coder-480b.