#P18457. Intro: Dawn of a New Era

Intro: Dawn of a New Era

Intro: Dawn of a New Era

题目描述

来自中国各地的朋友们,欢迎来到沈阳!作为出题人,我们和全体工作人员一样,深感荣幸,能够迎接大家参加这场精心准备的赛事,并共同见证东北大学(NEU)连续第九年举办 ICPC 沈阳区域赛。

过去几年对许多人来说都充满挑战。人类社会经历了新冠疫情,我们与之抗争并取得胜利。人类仍然经受着考验,仿佛“暗夜嚎叫者”侵蚀了某些人的心智。我们所在的这所可爱的大学,也刚刚圆满结束百年校庆,翻开了下一个百年的新篇章。这些经历启发了这道开场题的命名。我们衷心希望,每个人都能为梦想不断奋斗,而不甘成为时代的眼泪;也希望大家能用新时代的技术治愈世界,而不是将文明引向落日。

作为东北大学百年校庆的重要组成部分,无人机表演以缤纷色彩点亮夜空,创造出一幅幅令人惊叹的空中画卷。在这道开场题中,你将遇到一个与之有关、看起来仿佛是 NP 困难的问题。

东北大学无人机表演:原题图片

假设无人机表演共有 nn 个场景。每个场景的调色板可以用一个整数集合描述,每个整数标识一种颜色。我们称一个场景调色板中整数值最大的颜色为该场景的 主色。

无人机操作员希望重新安排这些场景的播放顺序。对于重新排序后的每一对相邻场景,如果前一个场景的主色出现在后一个场景的调色板中,就产生一次转场。请构造一个场景排列,使转场总次数尽可能多。

形式化地,令 SiS_i 表示第 ii 个场景的颜色集合,需要构造一个排列 p1,p2,…,pnp_1,p_2,\ldots,p_n,使

$$\sum_{i=1}^{n-1}\bigl[\max(S_{p_i})\in S_{p_{i+1}}\bigr]$$

在所有长度为 nn 的排列中最大。其中,条件为真时方括号的值为 11,否则为 00。

长度为 nn 的排列是由 nn 个整数组成的序列,其中 11 到 nn 每个整数恰好出现一次。注意:条件要求的是前一个场景的最大色属于下一个集合,仅有任意一种共同颜色并不足以产生转场。

输入格式

第一行包含一个整数 nn(2≤n≤1052\le n\le10^5),表示场景数量。

接下来 nn 行,第 ii 行先包含整数 mim_i(mi≥1m_i\ge1),表示第 ii 个调色板的颜色数量;然后给出 mim_i 个互不相同的整数 ai,1,ai,2,…,ai,mia_{i,1},a_{i,2},\ldots,a_{i,m_i}(0≤ai,j≤1090\le a_{i,j}\le10^9),分别标识其中的颜色。

保证 ∑i=1nmi≤2×105\sum_{i=1}^n m_i\le2\times10^5。颜色 00 合法,输入中各调色板的颜色无需有序。没有外层测试组数。

输出格式

第一行输出一个整数,表示能取得的最大转场次数。

第二行输出一个长度为 nn 的排列 p1,p2,…,pnp_1,p_2,\ldots,p_n,表示场景播放顺序;第 ii 个时段播放场景 pip_i。构造必须取得第一行所报告的最大值。若有多个最优排列,输出任意一个即可。

原样例 1

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

原样例 2

3
1 1
1 2
1 3
0
1 2 3

原样例说明

第一个样例中,场景 44 到场景 22、场景 22 到场景 33、场景 11 到场景 55 都能产生转场。

第二个样例中,没有两个场景具有共同颜色,因此任意长度为 33 的排列都可接受。