QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB Total points: 100

#9618. 神奇的耳语

Statistics

一群朋友想要玩“神奇耳语”游戏,在这个游戏中,秘密短语根据以下规则在人群中传递:

你有 $N \times M$ 个人,被分成 $M$ 个组,每组 $N$ 人。一个秘密短语被分为 $N$ 个不同的消息,第 1 组的每个成员接收一条不同的消息。随后,消息从第 1 组传到第 2 组,再从第 2 组传到第 3 组,以此类推,直到最终从第 $M-1$ 组传到第 $M$ 组。短语中的每条消息都必须被传递,但每个人最多只能听到一条消息。

为了让观察者更难追踪消息,第 $i$ 组的每个人都会表现得好像在向第 $i+1$ 组的至多 $N$ 个人耳语。实际上,只有其中一个人会听到消息——对于其余的人,发送者只是假装在耳语。这样,观察者就无法判断第 $i+1$ 组中究竟是谁收到了消息。第 $i$ 组的人已经安排好,使得第 $i+1$ 组的每个人都能恰好听到一条消息。

当所有消息到达第 $M$ 组时,它们会被大声读出。结果发现,除了其中一条消息被替换成了一个粗鲁的词汇外,其余消息都已成功接收。人 $A$ 最初持有那条丢失的消息,而人 $B$ 是最终大声读出那个粗鲁词汇的人。你不知道替换是在哪个阶段发生的。谁可能是这场恶作剧的始作俑者?你不知道消息是如何传递的,你只知道哪些人之间表现出了耳语的行为。

输入格式

第一行包含四个整数 $N, M, A, B$,如题目所述。 人的编号从 $0$ 到 $(N \times M) - 1$,其中人 $p$ 属于第 $\lfloor p/N \rfloor + 1$ 组。($\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。)

接下来有 $N \times (M - 1)$ 行。第 $i$ 行描述了第 $i$ 个人表现出向谁耳语。 每行以一个数字 $K_i$ 开头,表示第 $i$ 个人表现出向其耳语的人数。随后是 $K_i$ 个整数 $R_{i,0} \dots R_{i,K_i-1}$,指定了这些人是谁。由于这些人总是属于第 $i$ 个人所在组的下一组,这些数字满足 $R_{i,j}/N = i/N + 1$。

输出格式

第一行输出一个整数 $S$,表示可能是恶作剧始作俑者的人数。接下来的 $S$ 行应列出这些人,每行一人,按编号升序排列。

数据范围

$2 \le N \le 20$ $2 \le M \le 1\,000$ 所有 $K_i$ 的总和不超过 $5\,000$ 输入描述了一种有效的耳语执行方式。

子任务 分值 附加约束
子任务 1 18 $N = 2$
子任务 2 16 $M = 3; N \le 8$
子任务 3 19 $M = 3$
子任务 4 47 无附加约束

样例

输入 1

2 3 1 5
1 3
1 2
2 5 4
2 4 5

输出 1

3
1
2
5

输入 2

3 3 0 6
1 4
1 5
1 3
1 7
2 6 7
1 8

输出 2

3
0
4
6

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.