JOI 2025 - Post Office
Xem PDFĐất nước JOI có \(N\) bưu điện, được đánh số từ \(1\) đến \(N\). Mỗi bưu điện được chỉ định đúng một bưu điện để gửi hàng đến: bưu điện \(i\) gửi hàng đến bưu điện \(P_i\). Có thể xảy ra trường hợp \(P_i = i\).
Nếu một kiện hàng được gửi đi từ bưu điện \(i\) vào thời điểm \(t\), kiện hàng đó sẽ đến bưu điện \(P_i\) vào thời điểm \(t + 1\). Tuy nhiên, trong thời gian đang gửi một kiện hàng, bưu điện đó không thể gửi đi một kiện hàng khác. Mỗi bưu điện có thể lưu giữ số lượng kiện hàng không giới hạn tại bất kỳ thời điểm nào.
Hiện có \(M\) kiện hàng cần được chuyển ở đất nước JOI. Kiện hàng thứ \(j\) đến bưu điện \(A_j\) vào thời điểm \(0\) và cuối cùng phải được chuyển đến bưu điện \(B_j\) đã được chỉ định.
Cho thông tin về các bưu điện và các kiện hàng, hãy xác định có thể chuyển tất cả các kiện hàng đến đúng bưu điện được chỉ định hay không. Nếu có thể, hãy tìm thời điểm sớm nhất mà kiện hàng cuối cùng đến được bưu điện được chỉ định của nó.
Dữ liệu vào
Dữ liệu vào có dạng:
N
P_1 P_2 ... P_N
M
A_1 B_1
A_2 B_2
...
A_M B_M
Dữ liệu ra
In trên một dòng thời điểm sớm nhất mà kiện hàng cuối cùng đến được bưu điện được chỉ định của nó, nếu có thể chuyển tất cả các kiện hàng đến đúng nơi. Nếu không thể, in ra -1.
Ràng buộc
- \(2 \le N \le 200\,000\).
- \(1 \le M \le 200\,000\).
- \(1 \le P_i \le N\) (\(1 \le i \le N\)).
- \(1 \le A_j, B_j \le N\) (\(1 \le j \le M\)).
- \(A_j \ne B_j\) (\(1 \le j \le M\)).
- Tất cả các giá trị trong dữ liệu vào đều là số nguyên.
Chấm điểm
- \(3\) điểm: \(N \le 3000\), \(M = 1\).
- \(9\) điểm: \(N \le 3000\), \(M \le 3000\).
- \(13\) điểm: \(P = (1, 1, 2, \ldots, N - 1)\) và \(\max(B_1, B_2, \ldots, B_M) < \min(A_1, A_2, \ldots, A_M)\).
- \(25\) điểm: \(P = (1, 1, 2, \ldots, N - 1)\).
- \(11\) điểm: \(P = (N, 1, 2, \ldots, N - 1)\).
- \(25\) điểm: \(P_1 = 1\), \(P_i < i\) với mọi \(2 \le i \le N\).
- \(14\) điểm: Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
5
1 1 2 3 4
3
3 2
3 1
3 1Output
3Giải thích
Chẳng hạn, có thể gửi các kiện hàng như sau để tất cả đều đến đúng bưu điện được chỉ định không muộn hơn thời điểm \(3\).
Ở thời điểm \(0\), các kiện hàng \(1, 2, 3\) đều ở bưu điện \(3\). Gửi kiện hàng \(2\) đến bưu điện \(2\).
Ở thời điểm \(1\), kiện hàng \(2\) ở bưu điện \(2\), còn các kiện hàng \(1, 3\) ở bưu điện \(3\). Từ bưu điện \(2\), gửi kiện hàng \(2\) đến bưu điện \(1\); đồng thời, từ bưu điện \(3\), gửi kiện hàng \(3\) đến bưu điện \(2\).
Ở thời điểm \(2\), kiện hàng \(2\) ở bưu điện \(1\), kiện hàng \(3\) ở bưu điện \(2\), còn kiện hàng \(1\) ở bưu điện \(3\). Từ bưu điện \(2\), gửi kiện hàng \(3\) đến bưu điện \(1\); đồng thời, từ bưu điện \(3\), gửi kiện hàng \(1\) đến bưu điện \(2\).
Ở thời điểm \(3\), các kiện hàng \(2, 3\) ở bưu điện \(1\), còn kiện hàng \(1\) ở bưu điện \(2\). Lúc này, tất cả các kiện hàng đều đã đến đúng nơi.
Không thể chuyển tất cả các kiện hàng đến đúng bưu điện được chỉ định không muộn hơn thời điểm \(2\), nên in ra \(3\).
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 3, 4, 6, 7\).
Ví dụ 2
Input
3
2 1 3
1
1 3Output
-1Giải thích
Dù gửi hàng theo cách nào, cũng không thể chuyển một kiện hàng từ bưu điện \(1\) đến bưu điện \(3\), nên in ra -1.
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(1, 2, 7\).
Ví dụ 3
Input
7
1 1 2 3 4 5 6
6
4 2
5 1
5 3
6 2
7 3
7 6Output
5Giải thích
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 4, 6, 7\).
Ví dụ 4
Input
4
4 1 2 3
4
4 1
4 1
2 3
2 3Output
4Giải thích
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 5, 7\).
Ví dụ 5
Input
7
1 1 1 3 3 4 4
5
6 1
6 3
7 1
5 1
5 1Output
5Giải thích
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 6, 7\).
Ví dụ 6
Input
11
3 1 2 5 6 7 8 4 4 5 10
6
2 1
9 8
11 8
10 4
5 6
5 7Output
6Giải thích
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 7\).
Nguồn
Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.
Kỳ thi:
- JOI 2025 - Vòng chung kết quốc gia (2 Tháng 2., 2025)
Bình luận