| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 17 | 3 | 3 | 25.000% |
In the JOI country, there are $N$ post offices, numbered from 1ドル$ to $N$. Each post office has an assigned ”destination,” and the destination of post office $i$ is post office $P_i$. Note that it is possible for $P_i = i$. If a package is sent from post office $i$ at time $t,ドル it will arrive at post office $P_i$ at time $t + 1$. However, a post office cannot send another package while it is in the process of sending a package. Each post office can store an unlimited number of packages at any given time.
Now, $M$ packages need to be delivered in the JOI country. The $j$-th package arrives at post office $A_j$ at time 0ドル,ドル and it must eventually be delivered to the assigned post office $B_j$. Given the information about the post offices and the packages, write a program to determine whether it is possible to deliver all the packages to their assigned post offices, and if so, find the smallest possible time at which the last package arrives at its assigned post office.
Read the following data from the standard input.
$N$
$P_1$ $P_2$ $\cdots$ $P_N$
$M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$
Output a single line to the standard output. If it is possible to deliver all the packages to their assigned post offices, output the smallest possible time at which the last package arrives at its assigned post office. Otherwise, output -1 instead.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | $N ≦ 3,円 000,ドル $M = 1$. |
| 2 | 9 | $N ≦ 3,円 000,ドル $M ≦ 3,円 000$. |
| 3 | 13 | $P = (1, 1, 2, \cdots , N − 1),ドル and $\max(B_1, B_2, \dots , B_M) < \min(A_1, A_2, \dots , A_M)$. |
| 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ドル ≦ i ≦ N$). |
| 7 | 14 | No additional constraints. |
5 1 1 2 3 4 3 3 2 3 1 3 1
3
For example, by sending the packages in the following way, all the packages can be delivered to their assigned post offices by time 3ドル$:
Since it is not possible to deliver all the packages to their assigned post offices by time 2ドル,ドル output 3ドル$.
This sample input satisfies the constraints of Subtasks 2, 3, 4, 6, 7.
3 2 1 3 1 1 3
-1
No matter how the packages are sent, it is impossible to deliver a package from post office 1ドル$ to post office 3ドル,ドル so output -1.
This sample input satisfies the constraints of Subtasks 1, 2, 7.
7 1 1 2 3 4 5 6 6 4 2 5 1 5 3 6 2 7 3 7 6
5
This sample input satisfies the constraints of Subtasks 2, 4, 6, 7.
4 4 1 2 3 4 4 1 4 1 2 3 2 3
4
This sample input satisfies the constraints of Subtasks 2, 5, 7.
7 1 1 1 3 3 4 4 5 6 1 6 3 7 1 5 1 5 1
5
This sample input satisfies the constraints of Subtasks 2, 6, 7.
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
This sample input satisfies the constraints of Subtasks 2, 7.