题目背景
翻译自 ROIR 2025 D2T3。
题目描述
重温一下个人参加 OI 比赛的原则:每道题都要有分!不能有题目得零分。
让我们模拟一个 OI 比赛的过程。假设比赛中有 n 道题目,第 i 道题目包含 ki 个子任务,第 i 道题目的第 j 个子任务可以获得 ci,j 分。子任务之间是独立的,因此你可以在每道题中选择任意数量的子任务来解答。但是,你不能一个子任务都不选,因为那样这道题得分就是 0 分,这违反了原则。
你想知道,是否可以在遵守原则的前提下,恰好获得 s 分。
输入格式
第一行输入两个整数 n 和 s(1≤n≤100000,1≤s≤100000),分别表示比赛中的题目数量和所需的总得分。接下来 2n 行输入题目的描述,每道题目的描述包含两行:
- 第 i 道题目的第一行包含一个整数 ki(1≤ki≤100000),表示第 i 道题目有多少个子任务。
- 第 i 道题目的第二行包含 ki 个整数 ci,1,ci,2,…,ci,ki(1≤ci,j≤100000),表示各个子任务的分值。
保证 k1+k2+⋯+kn≤100000,且 (k1+k2+⋯+kn)⋅s≤107。
输出格式
如果无解,输出 No
。
否则,第一行输出 Yes
。接下来,输出每道题目选择的子任务。
对于第 i 道题目,先输出一行一个整数 mi(1≤mi≤ki),表示你选择的子任务数量。接下来在下一行输出 mi 个不同的整数 pi,1,pi,2,…,pi,mi(1≤pi,j≤ki),表示你选择的第 i 道题目的子任务编号。
如果有多个方案可以获得恰好 s 分,可以输出其中任意一个。
2 4
1
2
2
3 1
No
2 4
1
2
2
2 1
Yes
1
1
1
1
提示
本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。
子任务 |
分数 |
特殊性质 |
1 |
8 |
n=1 |
2 |
10 |
n=2 |
3 |
6 |
k1+k2+⋯+kn≤20 |
4 |
ki=1 |
5 |
15 |
n⋅s≤100000, s≤1000 |
6 |
55 |
无 |