JOI 2023 - Tuyển chọn mùa xuân - Ngày 1

Vương quốc JOI có \(N\) thành phố, đánh số từ \(1\) đến \(N\), và \(N-1\) con đường, đánh số từ \(1\) đến \(N-1\). Đường \(i\) (\(1\le i\le N-1\)) nối hai thành phố \(A_i\) và \(B_i\) theo cả hai chiều. Có thể đi từ một thành phố bất kỳ đến bất kỳ thành phố nào khác bằng cách đi qua một số con đường.

Trên một số con đường có các trạm thu phí. Có tất cả \(M\) trạm, đánh số từ \(1\) đến \(M\). Trạm \(j\) (\(1\le j\le M\)) nằm trên đường \(P_j\). Để đi qua trạm này, phải trả một đồng tiền vàng hoặc \(C_j\) đồng tiền bạc.

Có \(Q\) người dân, đánh số từ \(1\) đến \(Q\). Người dân \(k\) (\(1\le k\le Q\)) có \(X_k\) đồng tiền vàng và \(Y_k\) đồng tiền bạc, muốn đi từ thành phố \(S_k\) đến thành phố \(T_k\). Vì tiền vàng có giá trị cao, mỗi người đều muốn giữ lại càng nhiều đồng tiền vàng càng tốt.

Cho thông tin về các thành phố, con đường, trạm thu phí và người dân. Với mỗi \(k\) (\(1\le k\le Q\)), hãy xác định người dân \(k\) có thể đi từ \(S_k\) đến \(T_k\) hay không. Nếu có thể, hãy tính số đồng tiền vàng lớn nhất mà người đó có thể giữ lại sau chuyến đi.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N M Q
A_1 B_1
A_2 B_2
...
A_{N-1} B_{N-1}
P_1 C_1
P_2 C_2
...
P_M C_M
S_1 T_1 X_1 Y_1
S_2 T_2 X_2 Y_2
...
S_Q T_Q X_Q Y_Q

Dữ liệu ra

Xuất \(Q\) dòng ra đầu ra chuẩn. Ở dòng thứ \(k\) (\(1\le k\le Q\)), nếu người dân \(k\) có thể đi từ \(S_k\) đến \(T_k\), xuất số đồng tiền vàng lớn nhất mà người đó có thể giữ lại. Nếu không thể, xuất -1.

Ràng buộc

• \(2\le N\le 100\,000\).
• \(1\le M\le 100\,000\).
• \(1\le Q\le 100\,000\).
• \(1\le A_i\le N\) với \(1\le i\le N-1\).
• \(1\le B_i\le N\) với \(1\le i\le N-1\).
• Có thể đi từ một thành phố bất kỳ đến bất kỳ thành phố nào khác qua các con đường.
• \(1\le P_j\le N-1\) với \(1\le j\le M\).
• \(1\le C_j\le 10^9\) với \(1\le j\le M\).
• \(1\le S_k\le N\) với \(1\le k\le Q\).
• \(1\le T_k\le N\) với \(1\le k\le Q\).
• \(S_k\ne T_k\) với \(1\le k\le Q\).
• \(0\le X_k\le 10^9\) với \(1\le k\le Q\).
• \(0\le Y_k\le 10^{18}\) với \(1\le k\le Q\).
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

1. \(10\) điểm: \(N\le 2\,000\), \(M\le 2\,000\), \(Q\le 2\,000\).
2. \(28\) điểm: \(C_1=C_2=\cdots=C_M\).
3. \(30\) điểm: \(A_i=i\), \(B_i=i+1\) với mọi \(1\le i\le N-1\).
4. \(32\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1

1
2
-1

10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3

3
6
6
7
7
3
1
2
2

8 7 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 4
3 7
2 10
5 2
4 1
4 4
5 6
6 3 7 69
7 1 5 55
3 1 6 8
8 2 5 45
4 6 4 45
6 1 3 33
2 1 0 19
3 7 2 31
7 1 2 31
7 2 4 58
8 3 5 63

7
5
5
5
4
2
0
2
1
4
5

8 7 11
1 8
1 4
3 1
3 6
6 7
2 1
5 2
5 5
5 8
4 7
6 6
4 1
6 4
1 7
4 7 2 18
2 4 5 1
4 2 1 32
1 5 7 21
2 5 0 50
8 4 4 33
1 7 6 16
4 8 7 18
1 2 8 13
5 4 10 42
7 1 6 40

1
3
1
7
0
4
5
7
8
10
6

Nguồn

JOI 2022/2023 Spring Training, Contest 1, bài Two Currencies, tác giả 菅井遼明 và 星井智仁.

Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.

Ở vương quốc JOI, mỗi năm có một lễ hội toàn quốc. Trong thời gian diễn ra lễ hội có tổng cộng \(N\) sự kiện, với lịch trình đã được ấn định. Lịch của \(N\) sự kiện được mô tả bởi hai dãy \(a,b\) có độ dài \(N\), thỏa mãn:

• Mỗi số nguyên từ \(1\) đến \(2N\) xuất hiện trong dãy \(a\) hoặc dãy \(b\).
• \(a_i<b_i\) với \(1\le i\le N\).
• \(a_i<a_{i+1}\) với \(1\le i\le N-1\).

Sự kiện thứ \(i\) bắt đầu sau \(a_i\) phút kể từ khi lễ hội bắt đầu và kết thúc sau \(b_i\) phút kể từ khi lễ hội bắt đầu.

Người tham gia có thể chọn bất kỳ sự kiện nào, nhưng không được tham gia hai sự kiện có thời gian chồng lấn. Lưu ý rằng tất cả các thời điểm bắt đầu và kết thúc của các sự kiện đều khác nhau.

JOI-kun muốn tham gia càng nhiều sự kiện càng tốt. Cho đến năm ngoái, cậu dùng máy tính để chọn các sự kiện theo thuật toán sau:

Với \(i=1,2,\ldots,N\), lần lượt thực hiện:

• Nếu thời gian của sự kiện thứ \(i\) không chồng lấn với thời gian của bất kỳ sự kiện nào đã chọn tham gia trước đó, chọn tham gia sự kiện thứ \(i\).
• Nếu không, không tham gia sự kiện thứ \(i\).

Sau khi học khoa học máy tính, JOI-kun nhận ra thuật toán trên không phải lúc nào cũng cho số sự kiện tham gia lớn nhất. Từ năm nay, cậu sẽ dùng một thuật toán cải tiến, luôn chọn được số sự kiện lớn nhất có thể tham gia.

JOI-kun muốn biết có bao nhiêu trường hợp mà thuật toán cải tiến cho số sự kiện tham gia lớn hơn thuật toán cũ.

Cho số nguyên \(N\) và một số nguyên tố lớn \(P\), hãy đếm số cặp dãy \(a,b\) mô tả lịch của \(N\) sự kiện mà thuật toán cải tiến cho số sự kiện tham gia lớn hơn. Vì kết quả có thể rất lớn, hãy xuất phần dư của kết quả khi chia cho \(P\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N P

Dữ liệu ra

Xuất một dòng ra đầu ra chuẩn chứa phần dư khi chia cho \(P\) của số cặp dãy \(a,b\) mô tả lịch của \(N\) sự kiện mà thuật toán cải tiến cho số sự kiện tham gia lớn hơn thuật toán cũ.

Ràng buộc

• \(1\le N\le 20\,000\).
• \(10^8<P<10^9\).
• \(P\) là số nguyên tố.
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

1. \(5\) điểm: \(N\le 5\).
2. \(5\) điểm: \(N\le 8\).
3. \(27\) điểm: \(N\le 30\).
4. \(14\) điểm: \(N\le 300\).
5. \(36\) điểm: \(N\le 3\,000\).
6. \(13\) điểm: Không có ràng buộc bổ sung.

Ví dụ

3 100000007

2

4 100000007

28

15 999999937

935834920

Nguồn

JOI 2022/2023 Spring Training, Contest 1, bài Festivals in JOI Kingdom 2, tác giả 渡邉雄斗.

Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.

Hộ chiếu là giấy tờ được sử dụng trên khắp thế giới khi một người nhập cảnh vào nước ngoài.

Trên một hành tinh có \(N\) quốc gia, đánh số từ \(1\) đến \(N\). Mỗi quốc gia phát hành một loại hộ chiếu. Người có hộ chiếu do quốc gia \(i\) (\(1\le i\le N\)) phát hành được nhập cảnh vào các quốc gia \(L_i,L_i+1,\ldots,R_i\). Luôn được nhập cảnh vào chính quốc gia đã phát hành hộ chiếu, tức là \(L_i\le i\le R_i\).

Bạn có một người bạn rất thích du lịch. Cậu ấy mơ ước đi vòng quanh thế giới, nhưng ban đầu chưa có hộ chiếu nào. Vì vậy, cậu dự định ghé thăm tất cả \(N\) quốc gia bằng cách lặp lại hai hành động sau:

• Nhận hộ chiếu do quốc gia mà cậu đang ở phát hành.
• Di chuyển đến một quốc gia mà cậu được nhập cảnh bằng một trong các hộ chiếu hiện có.

Khi nghe kế hoạch này, bạn muốn biết cậu ấy có thể thực hiện được hay không. Nếu có thể, số hộ chiếu ít nhất mà cậu cần nhận là bao nhiêu? Do không biết cậu đang sống ở đâu, bạn xét \(Q\) khả năng về quốc gia nơi cậu sống: \(X_1,X_2,\ldots,X_Q\).

Cho thông tin về các hộ chiếu và những khả năng về nơi ở. Với mỗi khả năng, hãy xác định cậu ấy có thể ghé thăm tất cả \(N\) quốc gia hay không; nếu có thể, hãy tính số hộ chiếu ít nhất cần nhận.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N
L_1 R_1
L_2 R_2
...
L_N R_N
Q
X_1
X_2
...
X_Q

Dữ liệu ra

Xuất \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) (\(1\le j\le Q\)) tương ứng với trường hợp người bạn sống ở quốc gia \(X_j\). Nếu có thể ghé thăm tất cả \(N\) quốc gia, xuất số hộ chiếu ít nhất cần nhận. Nếu không thể, xuất -1.

Ràng buộc

• \(2\le N\le 200\,000\).
• \(1\le L_i\le i\le R_i\le N\) với \(1\le i\le N\).
• \(1\le Q\le N\).
• \(1\le X_j\le N\) với \(1\le j\le Q\).
• \(X_j<X_{j+1}\) với \(1\le j\le Q-1\).
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

1. \(6\) điểm: \(Q=1\), \(X_1=1\).
2. \(16\) điểm: \(N\le 300\), \(Q=1\).
3. \(24\) điểm: \(N\le 2\,500\), \(Q=1\).
4. \(8\) điểm: \(N\le 2\,500\).
5. \(46\) điểm: Không có ràng buộc bổ sung.

Ví dụ

4
1 3
2 4
2 3
4 4
1
1

2

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

4

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

-1
2
1
2
-1

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

-1
-1
-1
-1

Nguồn

JOI 2022/2023 Spring Training, Contest 1, bài Passport, tác giả 米田寛峻 và 米田優峻.

Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.