trang chủ / đề bài / icpc25_reg_b

Tô hai màu bảng

Đề bài

Mô tả

Cho một bảng gồm r hàng và c cột, được chia thành r·c ô. Các hàng được đánh số từ 1 đến r, các cột được đánh số từ 1 đến c. Ký hiệu (i,j) là ô ở hàng thứ i và cột thứ j. Hai ô là kề nhau khi và chỉ khi chúng có chung một cạnh.

Một số cạnh chung giữa các cặp ô kề nhau được tô đậm.

Ta định nghĩa một đường đi từ ô (i1,j1) đến ô (ik,jk) là một dãy ô (i1,j1),(i2,j2),…,(ik,jk) trong đó hai ô liên tiếp kề nhau và cạnh chung của chúng không được tô đậm.

Ta định nghĩa một thành phần liên thông là một tập ô sao cho giữa hai ô bất kỳ trong tập luôn có đường đi, và không thể thêm bất kỳ ô nào vào tập mà vẫn giữ được tính chất này.

Bây giờ ta muốn tô bảng bằng hai màu Đỏ và Xanh, sao cho hai ô kề nhau thuộc hai thành phần liên thông khác nhau thì có màu khác nhau. Ta gọi một cách tô như vậy là một cách tô hai màu. Lưu ý rằng có thể không tồn tại cách tô hai màu nào.

Bạn cần xử lý q truy vấn thuộc một trong ba loại sau:

  1. H i j: nếu cạnh chung giữa hai ô (i,j) và (i+1,j) chưa được tô đậm thì tô đậm nó; ngược lại, xóa nét đậm của cạnh đó.
  2. V i j: nếu cạnh chung giữa hai ô (i,j) và (i,j+1) chưa được tô đậm thì tô đậm nó; ngược lại, xóa nét đậm của cạnh đó.
  3. ? i j: xét ba trường hợp:
    • nếu tồn tại một cặp ô kề nhau ở bất kỳ đâu trên bảng thuộc cùng một thành phần liên thông mà cạnh chung của chúng được tô đậm, in ra một dòng chứa xâu Oh no!;
    • ngược lại, nếu bảng không có cách tô hai màu nào, in ra một dòng chứa xâu Cannot!;
    • ngược lại, xét mọi cách tô hai màu trong đó ô (1,1) có màu Đỏ, tìm mọi màu có thể của ô (i,j). Nếu ô này có thể tô bằng cả hai màu, in ra GR. Nếu ô này chỉ có thể tô màu đỏ, in ra R; nếu chỉ có thể tô màu xanh, in ra G.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương r và c (1≤r·c≤3·105).

r+1 dòng tiếp theo mô tả bảng ban đầu theo các quy tắc sau:

  • Mỗi dòng gồm đúng 2c+1 ký tự, đánh số từ 1. Trong mỗi dòng:
    • mọi ký tự ở vị trí chẵn là dấu cách () hoặc dấu gạch dưới (_);
    • mọi ký tự ở vị trí lẻ là dấu cách () hoặc dấu gạch đứng (|).
  • Mọi ký tự ở vị trí chẵn của dòng đầu tiên và dòng cuối cùng đều là dấu gạch dưới, biểu diễn biên trên và biên dưới của bảng.
  • Mọi dấu gạch dưới trong dữ liệu, trừ các dấu nêu ở trên, biểu diễn một cạnh ngang được tô đậm giữa hai ô liên tiếp cùng cột: ký tự ở vị trí 2j của dòng thứ i+1 (với 1≤i<r) là cạnh dưới của ô (i,j).
  • Ký tự đầu tiên và ký tự cuối cùng của mọi dòng (trừ dòng đầu tiên) là dấu gạch đứng, biểu diễn biên trái và biên phải của bảng.
  • Mọi dấu gạch đứng trong dữ liệu, trừ các dấu nêu ở trên, biểu diễn một cạnh dọc được tô đậm giữa hai ô liên tiếp cùng hàng: ký tự ở vị trí 2j+1 của dòng thứ i+1 (với 1≤j<c) là cạnh phải của ô (i,j).

Dòng tiếp theo chứa một số nguyên q (1≤q≤3·105): số truy vấn. q dòng tiếp theo mô tả các truy vấn, mỗi dòng thuộc một trong ba loại như mô tả ở trên:

  1. H i j (1≤i<r, 1≤j≤c),
  2. V i j (1≤i≤r, 1≤j<c),
  3. ? i j (1≤i≤r, 1≤j≤c).

Dữ liệu ra

Với mỗi truy vấn loại 3, in ra một dòng như mô tả ở trên.

Ràng buộc

  • 1≤r·c≤3·105.
  • 1≤q≤3·105.

Ví dụ

Input Output Giải thích
4 4
 _ _ _ _ 
|| _| |
| |_    |
|| |  |
|_ _ _ _|
8
? 4 4
H 3 4
? 4 4
H 2 2
V 3 2
H 3 3
H 3 4
? 4 4
Oh no!
Cannot!
R
Truy vấn loại 3 thứ nhất (truy vấn thứ 1): hai ô (3,3) và (4,3) thuộc cùng một thành phần liên thông nhưng cạnh chung của chúng được tô đậm. Trước truy vấn loại 3 thứ hai (truy vấn thứ 3), có thể chứng minh không tồn tại cách tô hai màu. Ở truy vấn loại 3 thứ ba (truy vấn thứ 8), cách tô hai màu duy nhất là: các ô (1,2), (1,3), (2,1), (3,1) màu Xanh, mọi ô còn lại màu Đỏ.
2 3
 _ _ _ 
|     |
|_ _ _|
7
? 2 3
V 1 1
? 2 3
H 1 1
? 1 1
? 2 1
? 1 2
R
Oh no!
R
G
G
Ví dụ bổ sung (không có trong đề gốc). Ban đầu không có cạnh nào bên trong bảng được tô đậm: cả bảng là một thành phần, ô (2,3) màu Đỏ. Sau khi tô đậm cạnh giữa (1,1) và (1,2), hai ô này vẫn thuộc cùng một thành phần. Sau khi tô đậm thêm cạnh giữa (1,1) và (2,1), ô (1,1) tách thành một thành phần riêng màu Đỏ, các ô còn lại màu Xanh.

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