[AdditionalFile4777.zip](file://AdditionalFile4777.zip?type=additional_file)

P11666 [JOI 2025 Final] 邮局 / Post Office

题目背景

译自 第24回日本情報オリンピック 本選 T5。

题目描述

有一张 $N$ 个节点 $N$ 条边的有向图，节点标号 $1\sim N$。

第 $i$ 条边从节点 $i$ 指向节点 $P_i$（注意，可能出现 $i=P_i$ 的情况），需要花 $1$ 单位时间经过它。

有 $M$ 个包裹，第 $j$（$1\le j\le M$）个包裹要从节点 $A_j$ 运到节点 $B_j$。这些包裹全部从 $0$ 时刻开始运送。

每条边一次只能运送一个包裹。节点可以存储无限多个包裹。

判断：是否能够将所有包裹都运到目的地。如果可以，还要求出到达时间最晚的包裹的最早到达时刻。

输入格式

如下所示：

$N$
$P_1$ $P_2$ $\cdots$ $P_N$
$M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

输出格式

如果无法运到，输出一行一个 $\texttt{-1}$。

否则输出一行一个整数，表示到达时间最晚的包裹的最早到达时刻。

输入输出样例 #1

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

3
2 1 3
1
1 3

输出 #2

-1

输入输出样例 #3

输入 #3

7
1 1 2 3 4 5 6
6
4 2
5 1
5 3
6 2
7 3
7 6

输出 #3

5

输入输出样例 #4

输入 #4

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

输出 #4

4

输入输出样例 #5

输入 #5

7
1 1 1 3 3 4 4
5
6 1
6 3
7 1
5 1
5 1

输出 #5

5

输入输出样例 #6

输入 #6

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

输出 #6

6

说明/提示

样例解释

样例 $1$ 解释

该样例满足子任务 $2,3,4,6,7$ 的限制。

样例 $2$ 解释

该样例满足子任务 $1,2,7$ 的限制。

样例 $3$ 解释

该样例满足子任务 $2,4,6,7$ 的限制。

样例 $4$ 解释

该样例满足子任务 $2,5,7$ 的限制。

样例 $5$ 解释

该样例满足子任务 $2,6,7$ 的限制。

样例 $6$ 解释

该样例满足子任务 $2,7$ 的限制。

数据范围

• $2\le N\le 2\times 10^5$。
• $1\le M\le 2\times 10^5$。
• $1\le P_i\le N$（$1\le i\le N$）。
• $1\le A_i,B_i\le N$（$1\le i\le M$）。
• $A_i\neq B_i$（$1\le i\le M$）。
• 输入的值全部是整数。

子任务

1. （3pts）$N\le 3,000$，$M=1$。
2. （9pts）$N\le 3,000$，$M\le 3,000$。
3. （13pts）$P=(1,1,2,\cdots,N-1)$，$\max(B_1,B_2,\cdots,B_M)\lt \min(A_1,A_2,\cdots,A_M)$。
4. （25pts）$P=(1,1,2,\cdots,N-1)$。
5. （11pts）$P=(N,1,2,\cdots,N-1)$。
6. （25pts）$P_1=1$，$P_i\lt i$（$2\le i\le N$）。
7. （14pts）无额外限制。

#4777. 「JOI 2025 Final」邮局

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2025 Final T5 「郵便局 / Post Office」

在 JOI 国有 $N$ 个邮局，每个邮局从 $1$ 到 $N$ 编号。每个邮局都有一个唯一的发送目的地，邮局 $i$ 的发送目的地是邮局 $P_i$。值得注意的是，$P_i$ 也可能等于 $i$。如果在时刻 $t$ 从邮局 $i$ 发送一个包裹，那么在时刻 $t+1$ 包裹将到达邮局 $P_i$。但是，在发送包裹的过程中，无法从该邮局发送其他包裹。此外，每个邮局可以无限制地存放包裹。

现在，JOI 国有 $M$ 个包裹需要递送。第 $j$ 个包裹在时刻 $0$ 到达邮局 $A_j$，最终必须递送到指定的邮局 $B_j$。给定邮局和包裹的信息，编写一个程序，判断是否可以将所有包裹递送到指定的邮局，如果可以，求出所有包裹到达指定邮局的最早时刻。

输入格式

第一行包含一个整数 $N$。

第二行包含用空格分隔的 $N$ 个整数 $P_1, P_2, \ldots P_N$。

第三行包含一个整数 $M$。

接下来 $M$ 行，每行包含两个用空格分隔的整数 $A_i,B_i$。

输出格式

如果可以将所有包裹递送到指定的邮局，输出最早的时刻值；否则，输出 $-1$。

样例 1

输入

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

输出

3

可以通过以下方式可以在时刻 $3$ 之前将所有包裹递送到指定的邮局：

• 在时刻 $0$，邮局 $3$ 有包裹 $1,2,3$。将包裹 $2$ 发送到邮局 $2$。
• 在时刻 $1$，邮局 $2$ 有包裹 $2$，邮局 $3$ 有包裹 $1$ 和 $3$。从邮局 $2$ 发送包裹 $2$ 到邮局 $1$，并从邮局 $3$ 发送包裹 $3$ 到邮局 $2$。
• 在时刻 $2$，邮局 $1$ 有包裹 $2$，邮局 $2$ 有包裹 $3$，邮局 $3$ 有包裹 $1$。从邮局 $2$ 发送包裹 $3$ 到邮局 $1$，并从邮局 $3$ 发送包裹 $1$ 到邮局 $2$。
• 在时刻 $3$，邮局 $1$ 有包裹 $2$ 和 $3$，邮局 $2$ 有包裹 $1$，此时所有包裹都已到达指定的邮局。

因为无法在时刻 $2$ 之前将所有包裹递送到指定的邮局，因此输出 $3$。

这个样例满足子任务 $2,3,4,6,7$ 的限制。

样例 2

输入

3
2 1 3
1
1 3

输出

-1

无论如何发送包裹，都无法从邮局 $1$ 将包裹送达邮局 $3$，因此输出 $-1$。

这个样例满足子任务 $1,2,7$ 的限制。

样例 3

输入

7
1 1 2 3 4 5 6
6
4 2
5 1
5 3
6 2
7 3
7 6

输出

5

这个样例满足子任务 $2,4,6,7$ 的限制。

样例 4

输入

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

输出

4

这个样例满足子任务 $2,5,7$ 的限制。

样例 5

输入

7
1 1 1 3 3 4 4
5
6 1
6 3
7 1
5 1
5 1

输出

5

这个样例满足子任务 $2,6,7$ 的限制。

样例 6

输入

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

输出

6

这个样例满足子任务 $2,7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 200000$。
• $1 \leq M \leq 200000$。
• $1 \leq P_i \leq N$ $(1 \leq i \leq N)$。
• $1 \leq A_j, B_j \leq N$ $(1 \leq j \leq M)$。
• $A_j \neq B_j$ $(1 \leq j \leq M)$。
• 输入的所有值均为整数。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$3$	$N \leq 3000, M=1$
$2$	$9$	$N \leq 3000, M \leq 3000$
$3$	$13$	$P=(1,1,2, \cdots, N-1), \max \left(B_{1}, B_{2}, \ldots, B_{M}\right) < \min \left(A_{1}, A_{2}, \ldots, A_{M}\right)$
$4$	$25$	$P=(1,1,2, \cdots, N-1)$
$5$	$11$	$P=(N, 1,2, \cdots, N-1)$
$6$	$25$	$P_{1}=1, P_{i}<i$ $(2 \leq i \leq N)$
$7$	$14$	无附加限制