[ROIR 2021] 绳子 (Day 1)

Luogu

IDLGP9764

Time1000ms

Memory512MB

DifficultyP6

数学图论2021Special Judge图论建模欧拉回路ROIR（俄罗斯）

有 $n$ 根绳子，第 $i$ 根绳子长 $s_i$ cm，有 $m_i$ 个节点，第 $j$ 个节点在离绳子左端点 $p_{i,j}$ cm 处。试构造一组从左至右连接绳子的方案，设该方案的绳子顺序为 $q$，$q$ 显然会是 $1\sim n$ 的一个排列，且满足如下要求：将第 $q_i$ 根绳子的右端点与第 $q_{i+1}$ 根绳子的左端点相接后 $(1\le i<n)$，相邻的节点间的距离相等。显然有可能没有方案，这个时候请输出 `No`。 ## Input 第一行为一个整数 $n$。接下来共 $2\times n$ 行： - 第 $2\times i(1\le i\le n)$ 行为两个整数 $m_i$ 与 $s_i$。 - 第 $2\times i+1(1\le i\le n)$ 行为 $m_i$ 个整数 $p_{i,j}$。 ## Output 若可以构造一组方案，输出 `Yes`，接下来再输出一行 $n$ 个整数 $q_i$。若无解，输出 `No`。 [samples] ## Background **译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day1 T4 [ Антенна](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day1.pdf)**。 ## Note 【样例解释1】： ![](https://s1.ax1x.com/2023/04/28/p9lIjVH.png) ![p9lIOqe.png](https://s1.ax1x.com/2023/04/28/p9lIOqe.png) 【数据范围】：对于所有子任务，均有 $1\le n\le 10^5$，$1\le m_i\le 10^5$，$0\le s_i\le 10^9$，$0\le p_{i,1}<p_{i,2}<\cdots<p_{i,m_i}\le s_i$，$\sum m_i\le 10^5$。 | 子任务编号 |特殊限制| 分值 | | :-: | :-: | :--: | |$1$| $n\le 8$，$m_i=1$，$s_i\le 100$ | $8$ | |$2$|$n\le 8$，$s_i\le 100$| $8$ | |$3$|$n\le 10^3$| $21$ | |$4$|$\sum m_i>n$| $21$ | |$5$|$s_i\le 100$| $21$ | |$6$|无特殊限制| $21$ |

Samples

Input #1

Output #1

Yes
2 1 3

Input #2

1
1 7
5

Output #2

Yes
1

Input #3

1
3 10
2 5 9

Output #3

No

Input #4

Output #4

No

Input #5

Output #5

Yes
3 2 1 4

API Response (JSON)

{
  "problem": {
    "name": "[ROIR 2021] 绳子 (Day 1)",
    "description": {
      "content": "有 $n$ 根绳子，第 $i$ 根绳子长 $s_i$ cm，有 $m_i$ 个节点，第 $j$ 个节点在离绳子左端点 $p_{i,j}$ cm 处。 试构造一组从左至右连接绳子的方案，设该方案的绳子顺序为 $q$，$q$ 显然会是 $1\\sim n$ 的一个排列，且满足如下要求：将第 $q_i$ 根绳子的右端点与第 $q_{i+1}$ 根绳子的左端点相接后 $(1\\le i<n)$，相邻的节点间",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9764"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 根绳子，第 $i$ 根绳子长 $s_i$ cm，有 $m_i$ 个节点，第 $j$ 个节点在离绳子左端点 $p_{i,j}$ cm 处。\n\n试构造一组从左至右连接绳子的方案，设该方案的绳子顺序为 $q$，$q$ 显然会是 $1\\sim n$ 的一个排列，且满足如下要求：将第 $q_i$ 根绳子的右端点与第 $q_{i+1}$ 根绳子的左端点相接后 $(1\\le i<n)$，相邻的节点间...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments