Mô phỏng phát triển hệ thống metro
Đề bài
Mô tả
Thành phố TTT sôi động đang chứng kiến sự phát triển chưa từng có của ngành công nghệ, kéo theo tình trạng ùn tắc giao thông nghiêm trọng và nhiều thách thức về vận tải. Với vai trò Kỹ sư trưởng quy hoạch metro của Cơ quan Giao thông đô thị TTT, bạn được giao nhiệm vụ thiết kế và mô phỏng hệ thống metro hoàn chỉnh đầu tiên của thành phố.
Hiện tại TTT có ga metro theo quy hoạch, được nối bởi tuyến metro một chiều; các ga được đánh số từ đến . Cơ quan giao thông đã phê duyệt một dự án mở rộng metro nhiều giai đoạn nhằm xây dựng một mạng lưới giao thông ngầm hiệu quả. Hệ thống mô phỏng của bạn cần xử lý hai loại thao tác phát triển metro quan trọng sẽ được thực hiện qua các giai đoạn xây dựng khác nhau.
Nhiệm vụ của bạn là mô phỏng thao tác phát triển metro, đại diện cho các giai đoạn xây dựng và quyết định quy hoạch tuyến trong thực tế. Mỗi thao tác thuộc một trong hai loại sau.
Thao tác loại 1 (Mở rộng ga): 1 x d. Một ga metro mới được xây dựng trong giai đoạn mở rộng hiện tại, và được nối với ga đang có bằng một tuyến metro mới để đảm bảo kết nối mạng lưới.
- Nếu , tuyến metro mới có chiều từ ga đến ga mới (cho phép đi từ ga đang có đến ga mới).
- Nếu , tuyến metro mới có chiều từ ga mới đến ga (cho phép đi từ ga mới đến ga đang có).
Sau thao tác này, tăng thêm vì hệ thống metro giờ có ga cần quản lý.
Thao tác loại 2 (Kiểm tra kết nối tuyến): 2 x y. Trung tâm điều hành cần kiểm tra xem hành khách có thể đi từ ga đến ga bằng mạng metro hiện tại hay không. In ra Yes nếu có thể đi từ ga đến ga theo các tuyến metro đang có, ngược lại in ra No.
Với vai trò kỹ sư quy hoạch metro, bạn cần xử lý các thao tác này theo thời gian thực để giúp lãnh đạo cơ quan giao thông đưa ra quyết định đúng đắn về các giai đoạn mở rộng metro và tối ưu tuyến của TTT.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên (số ga ban đầu) và (số tuyến metro đang có).
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và : có một tuyến metro một chiều từ ga đến ga .
- Dòng tiếp theo chứa số nguyên : số thao tác cần mô phỏng.
- dòng tiếp theo, mỗi dòng mô tả một thao tác thuộc một trong hai loại trên.
Dữ liệu ra
Với mỗi thao tác loại 2 (kiểm tra kết nối tuyến), in ra Yes nếu có thể đi từ ga đến ga , ngược lại in ra No.
Ràng buộc
- Các giá trị , luôn là số hiệu của một ga đang tồn tại trong TTT tại thời điểm thao tác.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 1 2 2 3 3 1 6 2 1 3 1 2 0 2 1 4 2 4 1 1 3 1 2 5 1 |
Yes Yes No Yes |
Ban đầu các tuyến , , tạo thành vòng. Truy vấn : đi . Thao tác 1 2 0 xây ga với tuyến . Truy vấn : đi . Truy vấn : ga không có tuyến đi ra nên không được. Thao tác 1 3 1 xây ga với tuyến . Truy vấn : đi . |
| 4 3 1 2 3 2 3 4 9 1 2 0 1 5 1 1 5 0 2 6 7 2 7 6 1 1 1 2 8 7 2 3 6 2 3 7 |
Yes No Yes No Yes |
Ví dụ bổ sung (không có trong đề gốc). Các tuyến mới: , , , . Có và , ; không có đường từ đến và từ đến . |
Bình luận