#P11091. [ROI 2021 Day 1] 工作报告
[ROI 2021 Day 1] 工作报告
题目背景
翻译自 ROI 2021 D1T4。
公司中有 个员工,编号从 到 。编号为 的员工是公司的创始人,其他员工都有且只有一个直接上级。公司的组织结构形成了一棵树,每个节点的父节点是它的上级,而子节点是它的下属。拥有下属的员工被称为经理,其他员工被称为顾问。公司的结构保证每个经理最多有 个下属,包括创始人。
创始人决定向投资者们汇报最近产品改进的情况。每个改进都是来自公司的某个顾问的工作成果。所有改进按照它们发生的时间顺序进行编号。
每个顾问需要选择一个改进并向他的经理汇报。因此,每个顾问的报告仅包含一个改进。
每个经理,包括创始人在内,需要汇总他们下属的报告,并按照报告的顺序将它们直接连续地组合起来。例如,如果第一个经理的报告包含改进 ,而第二个经理的报告包含改进 ,那么可以得到两种组合结果: 或者 ,其他组合是不可能的。
题目描述
创始人希望以尽可能合理的方式讲述这些改进,因此他希望在他的报告中改进按照编号的升序排列。请帮助每个顾问选择要汇报的改进,并帮助每个经理选择组合下属报告的顺序,以使得创始人的报告中的改进能够按照时间顺序排列。
输入格式
第一行包含一个整数 (),表示公司的员工数量。接下来的 行描述每个员工,每行包含以下内容之一:
- 如果员工是经理或创始人,则以数字 开头,接下来是数字 (),表示该经理的下属数量,然后是 个不同的数字,范围在 到 ,表示是其下属的员工编号。
- 如果员工是顾问,则以数字 开头,接下来是数字 ,表示他可以汇报的改进数量,然后是 个不同的整数,范围在 到 ,表示对应改进的编号。
保证每个改进都仅被一个顾问提及,即所有顾问提到的改进都是不同的。
输出格式
如果无法组合报告,输出 No
。
如果能够组合报告,输出 Yes
,然后你可以按照员工编号的顺序输出以下内容:
- 如果员工是经理,则输出他的下属在组合报告中的顺序。
- 如果员工是顾问,则输出他需要汇报的改进编号。
注:如果不输出组合报告的方式但正确判断了是否能够组合报告,将会得到 的部分分。
6
1 3 5 4 6
2 3 10 61 60
2 2 80 20
2 2 40 70
1 2 3 2
2 4 30 90 91 92
Yes
5 6 4
10
20
40
2 3
30
3
1 2 2 3
2 1 1
2 1 2
Yes
5
1 2 2 3
2 1 2
1 2 4 5
2 1 1
2 1 3
No
提示
样例解释:
在样例二中,没有输出具体的组合方法,所以只能得到部分分。正确的输出应该是这样的:
Yes
2 3
1
2
在样例三中,每个顾问都只能选择那唯一的改进编号。第三位经理有两种可能的报告方式: 或 。第一位经理有四种可能的报告方式,考虑到第三位经理的所有报告可能性:$[1, 3] + [2] = [1, 3, 2],[2] + [1, 3] = [2, 1, 3],[3, 1 ] + [2] = [3, 1, 2],[2] + [3, 1] = [2, 3, 1]$,但是在这些报告中没有一个改进是按照时间顺序排序的。
数据范围:
对于 的数据, 且 。