trang chủ / đề bài / icpc22_mn_b

Cải tạo hệ thống giao thông

Đề bài

Mô tả

Thành phố Hồ Chí Minh là thành phố lớn nhất và đông dân nhất Việt Nam. Thành phố có n giao lộ (đánh số từ 1 đến n), được nối bởi m con đường hai chiều (đánh số từ 1 đến m). Mỗi con đường nối hai giao lộ và có một tải trọng nhất định. Một xe tải có trọng lượng w có thể đi trên con đường có tải trọng c nếu w≤c.

Thành phố đang chuẩn bị một kế hoạch cải tạo hệ thống giao thông. Trong quá trình cải tạo, tải trọng của một số con đường có thể tăng hoặc giảm.

Cho hệ thống giao thông hiện tại và q truy vấn, mỗi truy vấn thuộc một trong hai loại:

  • C i x: đổi tải trọng của con đường i thành x.
  • S a b w: kiểm tra xem một xe tải có trọng lượng w có thể đi từ giao lộ a đến giao lộ b hay không.

Dữ liệu vào

  • Dòng đầu tiên gồm ba số nguyên n, m, q.
  • Dòng thứ i trong m dòng tiếp theo gồm ba số nguyên u, v, ci: có một con đường nối u và v với tải trọng ci.
  • q dòng tiếp theo là các truy vấn theo định dạng ở trên.

Tải trọng của các con đường không bao giờ vượt quá 109, và có không quá 2000 truy vấn loại C.

Dữ liệu ra

Với mỗi truy vấn loại S, in ra YES hoặc NO trên một dòng.

Ràng buộc

  • 1≤n≤1000, 1≤m≤105, 1≤q≤105
  • 1≤u,v≤n, 1≤ci≤109
  • Truy vấn C: 1≤i≤m, 1≤x≤109; có không quá 2000 truy vấn loại C.
  • Truy vấn S: 1≤a,b≤n, 1≤w≤109

Ví dụ

Input Output Giải thích
3 4 6
1 2 3
2 3 3
2 1 1
1 2 1
S 1 2 4
S 2 3 2
C 1 4
S 1 2 4
C 2 1
S 2 3 2
NO
YES
YES
NO
Ban đầu mọi con đường giữa 1 và 2 có tải trọng nhỏ hơn 4. Sau khi con đường 1 có tải trọng 4, xe trọng lượng 4 đi được từ 1 đến 2. Sau khi con đường 2 (con đường duy nhất tới giao lộ 3) còn tải trọng 1, xe trọng lượng 2 không đến được 3.
4 4 6
1 2 5
2 3 2
3 4 5
1 4 1
S 1 3 2
S 1 3 3
C 4 7
S 1 3 3
C 3 1
S 1 3 3
YES
NO
YES
NO
Ví dụ bổ sung (không có trong đề gốc). Sau khi con đường 1−4 có tải trọng 7, xe trọng lượng 3 đi được theo 1→4→3; sau khi con đường 3−4 còn tải trọng 1 thì không còn đường nào.

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