题目详情题解（0）讨论（0）提交记录（0）

CFCF2146B.Merging the Sets

普及-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给你 nn 个集合 S1,S2,…,SnS_1, S_2, \ldots, S_n，其中每个集合里的元素是 11 到 mm 之间的整数。

你需要选择一些集合（可以一个都不选，也可以全选），使得从 11 到 mm 的每个整数至少在一个被选中的集合中出现。

请判断是否有至少三种不同的方式选择集合，使上述条件成立。

输入格式

每组测试数据包含多组测试用例。第一行为测试用例组数 tt（1≤t≤1041 \le t \le 10^4）。接下来是各组测试数据。

每个测试用例的第一行为两个整数 nn 和 mm（2≤n≤5⋅1042 \leq n \leq 5 \cdot 10^4，1≤m≤1051 \le m \leq 10^5），分别表示集合数和整数范围上界。

接下来有 nn 行，第 ii 行首先包含一个整数 lil_i（1≤li≤m1\le l_i \le m），表示第 ii 个集合的大小。

接下来一行有 lil_i 个整数 Si,1,Si,2,…,Si,liS_{i,1}, S_{i,2}, \ldots, S_{i, l_i}（1≤Si,1<Si,2<⋯<Si,li≤m1\le S_{i,1} < S_{i,2} < \cdots < S_{i, l_i} \le m），表示 SiS_i 的元素。

记 L=∑i=1nliL=\sum\limits_{i=1}^n l_i。保证：

  • 所有测试用例中 nn 的总和不超过 5⋅1045 \cdot 10^4；
  • 所有测试用例中 mm 的总和不超过 10510^5；
  • 所有测试用例中 LL 的总和不超过 2⋅1052 \cdot 10^5。

输出格式

对于每个测试用例，如果存在至少三种不同的选择集合的方案，输出 YES，否则输出 NO。

你的答案可以用大小写任意的形式输出，如 “yEs”，"yes"，"Yes" 和 "YES" 都会被认为是正解。

输入输出样例

  • 输入#1

    6
3 2
2 1 2
1 1
1 2
4 10
3 1 2 3
2 4 5
1 6
4 7 8 9 10
2 5
4 1 2 3 4
4 1 2 3 4
5 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 10
4 1 2 3 4
5 1 2 5 6 7
5 2 6 7 8 9
4 6 7 8 9
2 9 10
5 5
1 1
1 2
1 3
2 4 5
1 5

    输出#1

    YES
NO
NO
YES
YES
NO

说明/提示

在第一个测试用例中，存在 5≥35 \ge 3 种选择方案：

  • 只选 S1S_1 — 11 和 22 都包含在 S1S_1 中；
  • 选 S1S_1 和 S2S_2 — 11 包含在 S1S_1 和 S2S_2，22 包含在 S1S_1；
  • 选 S1S_1 和 S3S_3 — 11 包含在 S1S_1，22 包含在 S1S_1 和 S3S_3；
  • 选 S2S_2 和 S3S_3 — 11 包含在 S2S_2，22 包含在 S3S_3；
  • 选 S1S_1、S2S_2 和 S3S_3 — 11 包含在 S1S_1 和 S2S_2，22 包含在 S1S_1 和 S3S_3。

注意，单独选 S2S_2 是不合法的，因为 22 不包含在 S2S_2 中。

在第二个测试用例中，只有唯一的一种方式就是全部选上所有集合。

在第三个测试用例中，55 没有出现在任意一个集合中，因此无法选择满足条件的集合。

在第四个测试用例中，任选非空的集合组合都满足条件，所以方案数为 25−1=31≥32^5-1=31\ge3。

首页