JOI 2025 - Billiards - LQDOJ: Le Quy Don Online Judge

JOI 2025 - Billiards

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Bitaro đang chơi bi-a. Bi-a ở đất nước JOI là trò chơi sử dụng \(N\) viên bi được đánh số \(1, 2, \ldots, N\) đặt trên bàn, trên bàn có các lỗ để đưa bi vào. Một viên bi đã rơi vào lỗ sẽ không được đặt trở lại bàn, nên không thể đưa viên bi đó vào lỗ lần nữa. Mục tiêu của Bitaro là đưa vào lỗ một viên bi có số lớn nhất có thể.

Đưa bi vào lỗ đòi hỏi sự tập trung. Ban đầu, mức tập trung của Bitaro là \(X\). Khi đưa viên bi \(i\) (\(1 \le i \le N\)) vào lỗ, mức tập trung giảm đi \(A_i\). Nếu mức tập trung nhỏ hơn \(A_i\), Bitaro không thể đưa viên bi \(i\) vào lỗ.

Trò chơi này còn có quy tắc về thứ tự đưa bi vào lỗ. Cụ thể, nếu \(P_i = -1\) (\(1 \le i \le N\)), có thể đưa viên bi \(i\) vào lỗ bất cứ lúc nào, miễn là có đủ mức tập trung. Nếu \(P_i \ne -1\), để đưa viên bi \(i\) vào lỗ thì viên bi \(P_i\) phải đã được đưa vào lỗ trước đó.

Cho mức tập trung ban đầu của Bitaro và thông tin về từng viên bi, hãy xác định Bitaro có thể đưa ít nhất một viên bi vào lỗ hay không. Nếu có, hãy tìm số lớn nhất của một viên bi mà Bitaro có thể đưa vào lỗ.

Dữ liệu vào

Dữ liệu vào có dạng:

N X
A_1 A_2 ... A_N
P_1 P_2 ... P_N

Dữ liệu ra

In trên một dòng số lớn nhất của một viên bi mà Bitaro có thể đưa vào lỗ. Nếu Bitaro không thể đưa bất kỳ viên bi nào vào lỗ, in ra -1.

Ràng buộc

\(1 \le N \le 200\,000\).
\(1 \le X \le 10^{15}\).
\(1 \le A_i \le 10^9\) (\(1 \le i \le N\)).
\(1 \le P_i \le N\) hoặc \(P_i = -1\) (\(1 \le i \le N\)).
\(P_i \ne i\) (\(1 \le i \le N\)).
Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

\(6\) điểm: \(N \le 1000\), \(P_i = -1\) với mọi \(1 \le i \le N\).
\(9\) điểm: \(N \le 1000\), \(P_1 = -1\), \(P_i = i - 1\) với mọi \(2 \le i \le N\).
\(16\) điểm: \(N \le 1000\), \(P_i < i\) với mọi \(1 \le i \le N\).
\(20\) điểm: \(P_i < i\) với mọi \(1 \le i \le N\).
\(19\) điểm: \(N \le 1000\).
\(30\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

6 7
1 2 4 3 10 100
-1 -1 -1 -1 -1 -1

Output

Giải thích

Ban đầu, mức tập trung của Bitaro là \(7\). Vì \(P_i = -1\) với mọi \(1 \le i \le N\), Bitaro có thể đưa bất kỳ viên bi nào vào lỗ bất cứ lúc nào, miễn là có đủ mức tập trung.

Chẳng hạn, Bitaro có thể đưa viên bi \(4\) vào lỗ như sau:

Đầu tiên, đưa viên bi \(3\) vào lỗ. Mức tập trung giảm đi \(4\), còn lại \(3\).
Tiếp theo, đưa viên bi \(4\) vào lỗ. Mức tập trung giảm đi \(3\), còn lại \(0\).

Bitaro không thể đưa viên bi \(5\) hay \(6\) vào lỗ. Vì vậy, số lớn nhất của một viên bi mà Bitaro có thể đưa vào lỗ là \(4\).

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(1, 3, 4, 5, 6\).

Ví dụ 2

Input

5 12
1 2 3 5 8
-1 1 2 3 4

Output

Giải thích

Ban đầu, mức tập trung của Bitaro là \(12\). Chẳng hạn, Bitaro có thể đưa viên bi \(4\) vào lỗ như sau:

Đầu tiên, đưa viên bi \(1\) vào lỗ. Vì \(P_1 = -1\), viên bi \(1\) có thể được đưa vào lỗ bất cứ lúc nào. Mức tập trung giảm đi \(1\), còn lại \(11\).
Tiếp theo, đưa viên bi \(2\) vào lỗ. Vì \(P_2 = 1\) và viên bi \(1\) đã được đưa vào lỗ, có thể đưa viên bi \(2\) vào lỗ. Mức tập trung giảm đi \(2\), còn lại \(9\).
Tiếp theo, đưa viên bi \(3\) vào lỗ. Vì \(P_3 = 2\) và viên bi \(2\) đã được đưa vào lỗ, có thể đưa viên bi \(3\) vào lỗ. Mức tập trung giảm đi \(3\), còn lại \(6\).
Tiếp theo, đưa viên bi \(4\) vào lỗ. Vì \(P_4 = 3\) và viên bi \(3\) đã được đưa vào lỗ, có thể đưa viên bi \(4\) vào lỗ. Mức tập trung giảm đi \(5\), còn lại \(1\).

Bitaro không thể đưa viên bi \(5\) vào lỗ. Vì vậy, số lớn nhất của một viên bi mà Bitaro có thể đưa vào lỗ là \(4\).

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 3, 4, 5, 6\).

Ví dụ 3

Input

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

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(3, 4, 5, 6\).

Ví dụ 4

Input

2 1000000000000000
1 1
2 1

Output

-1

Giải thích

Vì \(P_1 = 2\), muốn đưa viên bi \(1\) vào lỗ thì viên bi \(2\) phải đã được đưa vào lỗ. Ngược lại, vì \(P_2 = 1\), muốn đưa viên bi \(2\) vào lỗ thì viên bi \(1\) phải đã được đưa vào lỗ. Do đó, Bitaro không thể đưa bất kỳ viên bi nào vào lỗ, 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 \(5, 6\).

Ví dụ 5

Input

9 2468024680
123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678
6 5 4 -1 3 2 1 9 8

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(5, 6\).

Nguồn

Bản dịch tiếng Việt từ đề 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.

Bình luận

Tải bình luận...

Không có bình luận nào.

Kỳ thi:

JOI 2025 - Vòng loại 2 (8 Tháng 12., 2024)