trang chủ / đề bài / icpc22_nat_a

Bài toán quản lý phiên bản

Đề bài

Mô tả

Trong kỹ thuật phần mềm, "hệ thống quản lý phiên bản" (VCS) có nhiệm vụ quản lý các thay đổi đối với một chương trình máy tính, một tài liệu hay các thông tin khác. Trong bài này, bạn cần cài đặt một VCS cho một đồ thị vô hướng.

Ban đầu, đồ thị có N đỉnh và 0 cạnh. VCS cần lưu giữ nhiều ảnh chụp (snapshot) của đồ thị. Các ảnh chụp được đánh chỉ số theo thứ tự thời gian bằng các số nguyên bắt đầu từ 0. Ảnh chụp ban đầu của đồ thị được tạo ngay từ đầu, có chỉ số 0. Sau đó bạn cần thực hiện Q thao tác trên đồ thị. Mỗi thao tác thuộc một trong các loại sau:

  • ADD u v: thêm một cạnh mới nối hai đỉnh u và v;
  • CHECK u v: trên đồ thị hiện tại, kiểm tra hai đỉnh u và v có thuộc cùng một thành phần liên thông hay không;
  • COMMIT: tạo một ảnh chụp mới của đồ thị hiện tại;
  • QUERY s u v: trên ảnh chụp thứ s, kiểm tra hai đỉnh u và v có thuộc cùng một thành phần liên thông hay không.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên N và Q (1≤N,Q≤2·105). Mỗi dòng trong Q dòng tiếp theo mô tả một thao tác theo một trong các dạng sau:

  • A u v (1≤u,v≤N): thao tác ADD;
  • ? u v (1≤u,v≤N): thao tác CHECK;
  • C: thao tác COMMIT;
  • Q s u v (1≤u,v≤N, 0≤s<S, trong đó S là số ảnh chụp đã được tạo tính đến thời điểm đó): thao tác QUERY.

Dữ liệu ra

Với mỗi thao tác CHECK hoặc QUERY, theo đúng thứ tự, in ra ký tự Y nếu hai đỉnh u và v thuộc cùng một thành phần liên thông, và ký tự N trong trường hợp ngược lại. Các ký tự được in liền nhau trên một dòng.

Ràng buộc

  • 1≤N,Q≤2·105.
  • 1≤u,v≤N; u có thể bằng v.

Ví dụ

Input Output Giải thích
4 9
A 1 2
? 1 2
Q 0 1 2
C
Q 1 1 2
A 1 3
C
Q 1 1 3
Q 2 1 3
YNYNY Ảnh chụp 0 chưa có cạnh nào. Sau khi thêm cạnh (1,2): đồ thị hiện tại có 1 và 2 liên thông (Y) nhưng ảnh chụp 0 thì không (N). Ảnh chụp 1 có cạnh (1,2) (Y). Sau khi thêm cạnh (1,3) và tạo ảnh chụp 2: ảnh chụp 1 không có cạnh (1,3) (N), còn ảnh chụp 2 thì có (Y).
3 6
? 2 2
A 2 3
C
A 1 2
Q 1 1 3
? 1 3
YNY Một đỉnh luôn liên thông với chính nó. Ảnh chụp 1 chỉ có cạnh (2,3) nên 1 và 3 chưa liên thông, còn trên đồ thị hiện tại thì đã liên thông.

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