JOI 2025 - Mi Teleférico

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
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: 2500 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

La Paz, thủ đô của Bolivia, nổi tiếng không chỉ là một điểm du lịch mà còn nhờ mạng lưới cáp treo mang tên Mi Teleférico. Bạn đến La Paz du lịch và muốn tham quan càng nhiều nơi càng tốt. Trong bài toán này, ta xét tình huống được đơn giản hóa như sau.

La Paz có \(N\) ga cáp treo, được đánh số từ \(1\) đến \(N\) theo thứ tự độ cao tăng dần. Có \(M\) tuyến cáp treo một chiều, được đánh số từ \(1\) đến \(M\), và \(P\) công ty cáp treo, được đánh số từ \(1\) đến \(P\). Mỗi tuyến do một công ty quản lý. Tuyến \(i\) (\(1 \le i \le M\)) đi từ ga \(A_i\) đến ga \(B_i\) và do công ty \(C_i\) quản lý. Mỗi tuyến luôn đi từ ga thấp hơn đến ga cao hơn, tức là \(A_i<B_i\).

Để thuận tiện cho hành khách, cơ quan giao thông La Paz phát hành vé đi không giới hạn. Trên mỗi vé có hai số nguyên \(l,r\) thỏa mãn \(1 \le l \le r \le P\). Vé cho phép người sở hữu đi các tuyến do các công ty \(l,l+1,\ldots,r\) quản lý. Nói cách khác, với \(1 \le i \le M\), có thể dùng vé để đi tuyến \(i\) nếu \(l \le C_i \le r\). Một vé có thể được dùng cho nhiều tuyến. Ta gọi vé này là vé \((l,r)\).

Có \(Q\) du khách đến La Paz, được đánh số từ \(1\) đến \(Q\). Du khách \(j\) (\(1 \le j \le Q\)) có vé \((L_j,R_j)\) và \(X_j\) boliviano tiền mặt.

Mục tiêu của mỗi du khách là bảo đảm rằng từ ga \(1\) có thể đi đến từng ga, chỉ sử dụng các tuyến mà vé của mình cho phép đi. Để đạt mục tiêu này, du khách \(j\) (\(1 \le j \le Q\)) có thể đổi vé theo các bước sau, nhưng mỗi người chỉ được đổi tối đa một lần:

  1. Chọn hai số nguyên \(l',r'\) thỏa mãn \(1 \le l' \le r' \le P\).
  2. Đổi vé \((L_j,R_j)\) lấy vé \((l',r')\), với phí đổi vé là \(|L_j-l'|+|R_j-r'|\) boliviano.

Cho thông tin về các ga, các tuyến và các du khách, hãy xác định với từng du khách liệu họ có thể đạt được mục tiêu mà không chi quá số tiền mặt đang có hay không.

Dữ liệu vào

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

N M P
A_1 B_1 C_1
A_2 B_2 C_2
...
A_M B_M C_M
Q
L_1 R_1 X_1
L_2 R_2 X_2
...
L_Q R_Q X_Q

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa Yes nếu du khách \(j\) có thể đạt được mục tiêu trong phạm vi số tiền đang có, hoặc No nếu không thể.

Ràng buộc

  • \(2 \le N \le 300\,000\).
  • \(1 \le M \le 300\,000\).
  • \(1 \le P \le 10^9\).
  • \(1 \le A_i<B_i \le N\) (\(1 \le i \le M\)).
  • \(1 \le C_i \le P\) (\(1 \le i \le M\)).
  • \(1 \le Q \le 400\,000\).
  • \(1 \le L_j \le R_j \le P\) (\(1 \le j \le Q\)).
  • \(0 \le X_j \le 10^9\) (\(1 \le j \le Q\)).
  • Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

  1. 7 điểm: \(N \le 50\), \(M \le 50\), \(Q \le 50\), \(X_j=0\) (\(1 \le j \le Q\)).
  2. 8 điểm: \(P \le 10\).
  3. 11 điểm: \(P \le 100\).
  4. 23 điểm: \(P \le 300\,000\), \(X_j=0\) (\(1 \le j \le Q\)).
  5. 9 điểm: \(P \le 300\,000\).
  6. 22 điểm: \(N \le 8\,000\), \(M \le 8\,000\).
  7. 20 điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
4
3 7 0
5 6 0
3 4 0
1 9 0
Output 
Yes
No
No
Yes
Giải thích

Du khách \(1\) ban đầu có vé \((3,7)\) và \(0\) boliviano tiền mặt. Người này có thể đạt mục tiêu mà không cần đổi vé. Vé \((3,7)\) cho phép đi bốn tuyến \(1,2,3,4\), nhờ đó có thể đi từ ga \(1\) đến từng ga như sau:

  • Đi tuyến \(3\) để đi từ ga \(1\) đến ga \(2\).
  • Lần lượt đi các tuyến \(1,4\) để đi theo lộ trình \(1 \to 2 \to 3\).
  • Lần lượt đi các tuyến \(3,2\) để đi theo lộ trình \(1 \to 2 \to 4\).

Vì vậy, dòng thứ nhất là Yes.

Du khách \(2\) ban đầu có vé \((5,6)\) và \(0\) boliviano tiền mặt. Vé này chỉ cho phép đi hai tuyến \(3,4\), nên không thể đi từ ga \(1\) đến ga \(4\). Hơn nữa, vì không có tiền mặt, người này không thể đổi sang một vé khác. Do đó, du khách \(2\) không thể đạt mục tiêu, và dòng thứ hai là No.

Du khách \(3\) cũng không thể đạt mục tiêu, còn du khách \(4\) có thể đạt mục tiêu. Vì vậy, dòng thứ ba là No và dòng thứ tư là Yes.

Ví dụ này thỏa mãn ràng buộc của tất cả các subtasks.

Ví dụ 2

Input 
4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
3
5 6 10
3 4 1
7 8 3
Output 
Yes
No
Yes
Giải thích

Thông tin về các ga và các tuyến giống ví dụ \(1\).

Du khách \(1\) ban đầu có vé \((5,6)\) và \(10\) boliviano tiền mặt. Người này có thể đạt mục tiêu bằng cách đổi vé như sau:

  1. Chọn \(l'=1,r'=5\), thỏa mãn \(1 \le l' \le r' \le P\).
  2. Đổi vé \((5,6)\) lấy vé \((1,5)\) với phí \(|5-1|+|6-5|=5\) boliviano.

Vì vậy, dòng thứ nhất là Yes.

Du khách \(2\) ban đầu có vé \((3,4)\) và \(1\) boliviano tiền mặt. Dù đổi vé theo cách nào trong phạm vi số tiền đang có, người này cũng không thể đạt mục tiêu. Vì vậy, dòng thứ hai là No.

Du khách \(3\) có thể đạt mục tiêu, nên dòng thứ ba là Yes.

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

Ví dụ 3

Input 
3 1 1000000000
1 2 6
1
1 1000000000 1000000000
Output 
No
Giải thích

Với các tuyến đã cho, không thể đi từ ga \(1\) đến ga \(3\). Vì vậy, du khách không thể đạt mục tiêu bất kể sở hữu vé nào.

Ví dụ này thỏa mãn ràng buộc của các subtasks \(6,7\).

Ví dụ 4

Input 
5 9 2000
2 3 1814
2 3 457
1 2 1226
3 4 1354
1 5 1050
1 2 1725
2 3 1383
1 5 1626
1 4 1795
5
850 1872 128
82 428 1217
487 924 573
1639 1926 202
202 420 25
Output 
Yes
Yes
Yes
Yes
No
Giải thích

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

Nguồn

Đề bài Mi Teleférico, JOI 2024/2025, vòng chung kết quốc gia, bài 3 (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

Mới nhất
Tải bình luận...

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

Kỳ thi: