Cung đường leo núi
Đề bài
Mô tả
Khu du lịch sinh thái Pù Luông có điểm dừng được đánh số từ đến và cung đường mòn hai chiều. Cung đường thứ nối hai điểm dừng và , có độ gian nan . Giữa hai điểm dừng có thể có nhiều cung đường khác nhau, và mạng đường mòn không nhất thiết liên thông.
Điểm dừng thứ có điểm phong cảnh .
Một nhóm khách có sức bền chỉ dám đi những cung đường có độ gian nan không vượt quá . Nếu nhóm khởi hành từ điểm dừng thì tập điểm dừng mà nhóm tới được là tập các điểm dừng có thể đến từ bằng cách chỉ dùng các cung đường có độ gian nan không vượt quá ; theo quy ước, bản thân điểm dừng luôn tới được.
Ban quản lý cần xử lý yêu cầu xuất hiện lần lượt theo thời gian, mỗi yêu cầu thuộc một trong hai loại:
- Loại 1, dạng
1 i s: chấm lại điểm phong cảnh của điểm dừng , tức gán . - Loại 2, dạng
2 v x k: một nhóm khách có sức bền khởi hành từ điểm dừng . Hãy cho biết điểm phong cảnh lớn thứ trong các điểm dừng mà nhóm tới được. Ở đây lớn thứ được hiểu theo nghĩa sắp xếp các điểm phong cảnh của những điểm dừng tới được theo thứ tự không tăng rồi lấy giá trị thứ (các giá trị bằng nhau vẫn được tính riêng). Nếu số điểm dừng tới được nhỏ hơn thì ghi ra .
Yêu cầu: Hãy trả lời tất cả các yêu cầu loại 2.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên , , .
- Dòng thứ hai chứa số nguyên .
- Mỗi dòng trong dòng tiếp theo chứa ba số nguyên , , mô tả một cung đường mòn.
- Mỗi dòng trong dòng tiếp theo chứa một yêu cầu, theo một trong hai dạng:
1 i shoặc2 v x k. Có ít nhất một yêu cầu loại 2.
Dữ liệu ra
Với mỗi yêu cầu loại 2, ghi ra trên một dòng riêng một số nguyên là điểm phong cảnh lớn thứ cần tìm, hoặc nếu số điểm dừng tới được nhỏ hơn .
Ràng buộc
- ; ; .
- .
- ; ; .
- Yêu cầu loại 1: ; .
- Yêu cầu loại 2: ; ; .
Subtasks
- Subtask 1 ( số điểm): .
- Subtask 2 ( số điểm): không có yêu cầu loại 1 và mọi yêu cầu loại 2 đều có .
- Subtask 3 ( số điểm): không có yêu cầu loại 1.
- Subtask 4 ( số điểm): mạng đường mòn liên thông và mọi yêu cầu loại 2 đều có .
- Subtask 5 ( số điểm): .
- Subtask 6 ( số điểm): không có ràng buộc gì thêm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 4 6 5 3 9 1 7 4 1 2 2 2 3 5 3 4 1 5 6 3 2 1 2 1 2 1 5 2 2 4 1 2 1 3 2 2 1 5 2 2 5 2 3 |
5 5 1 3 -1 |
Mạng đường mòn gồm hai phần rời nhau: nối với nhau bởi các cung (độ gian nan ), (độ gian nan ), (độ gian nan ); và nối bởi cung (độ gian nan ). Điểm phong cảnh ban đầu là .2 1 2 1: với chỉ dùng được cung và cung , nên từ điểm tới được với các điểm phong cảnh . Giá trị lớn nhất là .2 1 5 2: với dùng được cả ba cung của phần thứ nhất, tới được với các điểm phong cảnh . Giá trị lớn thứ hai là .2 4 1 2: với chỉ dùng được cung , nên từ điểm tới được với các điểm phong cảnh . Giá trị lớn thứ hai là .1 3 2: điểm phong cảnh trở thành .2 1 5 2: vẫn tới được nhưng các điểm phong cảnh giờ là . Giá trị lớn thứ hai là .2 5 2 3: với không dùng được cung (độ gian nan ), nên từ điểm chỉ tới được chính nó. Số điểm dừng tới được là , ghi ra . |
| 8 7 8 4 8 4 6 2 8 5 3 1 2 3 2 3 3 1 2 7 3 4 6 5 6 2 6 7 4 4 5 9 2 1 3 3 2 4 5 1 2 7 4 3 1 2 1 2 3 6 2 2 5 9 6 2 5 8 4 2 8 9 2 |
4 6 2 4 2 -1 -1 |
Ví dụ bổ sung. Giữa điểm và điểm có hai cung (độ gian nan và ); điểm không có cung nào.2 1 3 3: đúng bằng độ gian nan của các cung , nên vẫn đi được; tới được với điểm , giá trị lớn thứ ba là (hai giá trị được tính riêng).2 4 5 1: cung có độ gian nan , chỉ tới được điểm , đáp số .2 7 4 3: tới được với điểm , giá trị lớn thứ ba là .1 2 1: .2 3 6 2: tới được với điểm , giá trị lớn thứ hai là .2 5 9 6: tới được cả điểm với điểm (theo thứ tự không tăng), giá trị thứ sáu là .2 5 8 4: cung có độ gian nan , chỉ tới được , có điểm nên ghi .2 8 9 2: điểm chỉ tới được chính nó, ghi . |
Bình luận