JOI 2023 - Two Currencies
Xem PDFVươ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.
- \(10\) điểm: \(N\le 2\,000\), \(M\le 2\,000\), \(Q\le 2\,000\).
- \(28\) điểm: \(C_1=C_2=\cdots=C_M\).
- \(30\) điểm: \(A_i=i\), \(B_i=i+1\) với mọi \(1\le i\le N-1\).
- \(32\) điểm: Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
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 1Output
1
2
-1Giải thích
Người dân \(1\) có thể đi từ thành phố \(3\) đến thành phố \(4\) như sau và giữ lại \(1\) đồng tiền vàng:
- Đi từ thành phố \(3\) đến thành phố \(1\) qua đường \(2\). Đường này có các trạm \(1,2\). Trả \(1\) đồng tiền vàng để qua trạm \(1\) và \(4\) đồng tiền bạc để qua trạm \(2\). Sau đó, người này còn \(1\) đồng tiền vàng và \(7\) đồng tiền bạc.
- Đi từ thành phố \(1\) đến thành phố \(2\) qua đường \(1\). Đường này không có trạm thu phí, nên vẫn còn \(1\) đồng tiền vàng và \(7\) đồng tiền bạc.
- Đi từ thành phố \(2\) đến thành phố \(4\) qua đường \(3\). Đường này có trạm \(3\); trả \(5\) đồng tiền bạc để đi qua. Sau đó, người này còn \(1\) đồng tiền vàng và \(2\) đồng tiền bạc.
Không có cách nào để người dân \(1\) hoàn thành chuyến đi và giữ lại từ \(2\) đồng tiền vàng trở lên, nên dòng đầu tiên là 1.
Người dân \(2\) có thể đi từ thành phố \(5\) đến thành phố \(3\) như sau và giữ lại \(2\) đồng tiền vàng:
- Đi từ thành phố \(5\) đến thành phố \(2\) qua đường \(4\). Đường này có trạm \(4\); trả \(1\) đồng tiền vàng để đi qua. Sau đó, người này còn \(3\) đồng tiền vàng và \(5\) đồng tiền bạc.
- Đi từ thành phố \(2\) đến thành phố \(1\) qua đường \(1\). Đường này không có trạm thu phí, nên vẫn còn \(3\) đồng tiền vàng và \(5\) đồng tiền bạc.
- Đi từ thành phố \(1\) đến thành phố \(3\) qua đường \(2\). Đường này có các trạm \(1,2\). Trả \(1\) đồng tiền vàng để qua trạm \(1\) và \(4\) đồng tiền bạc để qua trạm \(2\). Sau đó, người này còn \(2\) đồng tiền vàng và \(1\) đồng tiền bạc.
Không có cách nào để người dân \(2\) hoàn thành chuyến đi và giữ lại từ \(3\) đồng tiền vàng trở lên, nên dòng thứ hai là 2. Người dân \(3\) không thể đi từ thành phố \(2\) đến thành phố \(3\), nên dòng thứ ba là -1.
Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,4\).
Ví dụ 2
Input
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 3Output
3
6
6
7
7
3
1
2
2Giải thích
Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,4\).
Ví dụ 3
Input
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 63Output
7
5
5
5
4
2
0
2
1
4
5Giải thích
Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,3,4\).
Ví dụ 4
Input
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 40Output
1
3
1
7
0
4
5
7
8
10
6Giải thích
Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,4\).
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.
Kỳ thi:
- JOI 2023 - Tuyển chọn mùa xuân - Ngày 1 (19 Tháng ba, 2023)
Bình luận