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ó giao lộ (đánh số từ đến ), được nối bởi con đường hai chiều (đánh số từ đến ). 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 có thể đi trên con đường có tải trọng nếu .
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à truy vấn, mỗi truy vấn thuộc một trong hai loại:
- C : đổi tải trọng của con đường thành .
- S : kiểm tra xem một xe tải có trọng lượng có thể đi từ giao lộ đến giao lộ hay không.
Dữ liệu vào
- Dòng đầu tiên gồm ba số nguyên , , .
- Dòng thứ trong dòng tiếp theo gồm ba số nguyên , , : có một con đường nối và với tải trọng .
- 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á , và có không quá 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
- , ,
- ,
- Truy vấn C: , ; có không quá truy vấn loại C.
- Truy vấn S: ,
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 và có tải trọng nhỏ hơn . Sau khi con đường có tải trọng , xe trọng lượng đi được từ đến . Sau khi con đường (con đường duy nhất tới giao lộ ) còn tải trọng , xe trọng lượng không đến được . |
| 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 có tải trọng , xe trọng lượng đi được theo ; sau khi con đường còn tải trọng thì không còn đường nào. |
Bình luận