trang chủ / đề bài / tddn26_trekking

Cung đường leo núi

Đề bài

Mô tả

Khu du lịch sinh thái Pù Luông có N điểm dừng được đánh số từ 1 đến N và M cung đường mòn hai chiều. Cung đường thứ j nối hai điểm dừng uj và vj, có độ gian nan wj. 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ứ i có điểm phong cảnh si.

Một nhóm khách có sức bền x chỉ dám đi những cung đường có độ gian nan không vượt quá x. Nếu nhóm khởi hành từ điểm dừng v 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ừ v bằng cách chỉ dùng các cung đường có độ gian nan không vượt quá x; theo quy ước, bản thân điểm dừng v luôn tới được.

Ban quản lý cần xử lý Q 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 i, tức gán si:=s.
  • Loại 2, dạng 2 v x k: một nhóm khách có sức bền x khởi hành từ điểm dừng v. Hãy cho biết điểm phong cảnh lớn thứ k trong các điểm dừng mà nhóm tới được. Ở đây lớn thứ k đượ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ứ k (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 k thì ghi ra −1.

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 N, M, Q.
  • Dòng thứ hai chứa N số nguyên s1,s2,…,sN.
  • Mỗi dòng trong M dòng tiếp theo chứa ba số nguyên uj, vj, wj mô tả một cung đường mòn.
  • Mỗi dòng trong Q dòng tiếp theo chứa một yêu cầu, theo một trong hai dạng: 1 i s hoặc 2 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ứ k cần tìm, hoặc −1 nếu số điểm dừng tới được nhỏ hơn k.

Ràng buộc

  • 2≤N≤2·105; 1≤M≤2·105; 1≤Q≤2·105.
  • 1≤si≤109.
  • 1≤uj,vj≤N; uj≠vj; 1≤wj≤109.
  • Yêu cầu loại 1: 1≤i≤N; 1≤s≤109.
  • Yêu cầu loại 2: 1≤v≤N; 0≤x≤109; 1≤k≤N.

Subtasks

  • Subtask 1 (15% số điểm): N,M,Q≤1000.
  • Subtask 2 (15% 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ó k=1.
  • Subtask 3 (15% số điểm): không có yêu cầu loại 1.
  • Subtask 4 (15% số điểm): mạng đường mòn liên thông và mọi yêu cầu loại 2 đều có x≥maxwj.
  • Subtask 5 (20% số điểm): N,M,Q≤5·104.
  • Subtask 6 (20% 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: {1,2,3,4} nối với nhau bởi các cung 1−2 (độ gian nan 2), 2−3 (độ gian nan 5), 3−4 (độ gian nan 1); và {5,6} nối bởi cung 5−6 (độ gian nan 3). Điểm phong cảnh ban đầu là s=(5,3,9,1,7,4).
2 1 2 1: với x=2 chỉ dùng được cung 1−2 và cung 3−4, nên từ điểm 1 tới được {1,2} với các điểm phong cảnh 5,3. Giá trị lớn nhất là 5.
2 1 5 2: với x=5 dùng được cả ba cung của phần thứ nhất, tới được {1,2,3,4} với các điểm phong cảnh 9,5,3,1. Giá trị lớn thứ hai là 5.
2 4 1 2: với x=1 chỉ dùng được cung 3−4, nên từ điểm 4 tới được {3,4} với các điểm phong cảnh 9,1. Giá trị lớn thứ hai là 1.
1 3 2: điểm phong cảnh trở thành s=(5,3,2,1,7,4).
2 1 5 2: vẫn tới được {1,2,3,4} nhưng các điểm phong cảnh giờ là 5,3,2,1. Giá trị lớn thứ hai là 3.
2 5 2 3: với x=2 không dùng được cung 5−6 (độ gian nan 3), nên từ điểm 5 chỉ tới được chính nó. Số điểm dừng tới được là 1<3, ghi ra −1.
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 1 và điểm 2 có hai cung (độ gian nan 3 và 7); điểm 8 không có cung nào.
2 1 3 3: x=3 đúng bằng độ gian nan của các cung 1−2, 2−3 nên vẫn đi được; tới được {1,2,3} với điểm 4,8,4, giá trị lớn thứ ba là 4 (hai giá trị 4 được tính riêng).
2 4 5 1: cung 3−4 có độ gian nan 6>5, chỉ tới được điểm 4, đáp số 6.
2 7 4 3: tới được {5,6,7} với điểm 2,8,5, giá trị lớn thứ ba là 2.
1 2 1: s2:=1.
2 3 6 2: tới được {1,2,3,4} với điểm 4,1,4,6, giá trị lớn thứ hai là 4.
2 5 9 6: tới được cả 7 điểm 1..7 với điểm 8,6,5,4,4,2,1 (theo thứ tự không tăng), giá trị thứ sáu là 2.
2 5 8 4: cung 4−5 có độ gian nan 9>8, chỉ tới được {5,6,7}, có 3<4 điểm nên ghi −1.
2 8 9 2: điểm 8 chỉ tới được chính nó, ghi −1.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0