trang chủ / đề bài / icpc21_mt_o

Trò chơi gỗ

Đề bài

Mô tả

Quang và Tùng đang làm việc ở một xưởng gỗ. Hệ thống điện của xưởng có N ổ cắm đơn, mỗi ổ thuộc loại âm (-) hoặc dương (+). Trong xưởng có một máy cắt ghép C với hai phích cắm A và B. Bên trong máy là một tấm gỗ kích thước X×Y (X và Y là số lẻ) đang chờ xử lý.

  • Nếu A và B cắm vào hai ổ khác loại (tức là - + hoặc + -), C hoạt động như máy cắt: mỗi bước, máy cắt một tấm gỗ thành hai tấm, cả hai đều là hình chữ nhật có cạnh nguyên (vị trí và hướng của các tấm được giữ nguyên). Hai tấm sinh ra từ cùng một lần cắt được gọi là hai tấm anh em.
  • Nếu A và B cắm vào hai ổ cùng loại (tức là + + hoặc - -), C hoạt động như máy ghép: mỗi bước, máy ghép hai tấm anh em (cả hai hiện vẫn còn nguyên, chưa bị cắt tiếp) lại thành tấm gỗ đã bị cắt ra chúng. Tấm thu được lại có tấm anh em như trước khi bị cắt, nếu nó từng được sinh ra từ một lần cắt.

Nói cách khác, máy ghép chỉ hoàn tác được một lần cắt mà cả hai mảnh của nó còn nguyên.

Là những thí sinh từng vào chung kết thế giới, Quang và Tùng thường có quan điểm khác nhau về cùng một vấn đề. Họ không thống nhất được cách dùng máy. Đã có K bước được thực hiện trên tấm gỗ, nhưng giờ Quang và Tùng dừng làm việc vì bất đồng. Thay vì đánh nhau, họ quyết định chơi một trò chơi để tránh xung đột:

  • Họ vẽ M cạnh có hướng, mỗi cạnh nối hai ổ cắm, sao cho không có chu trình (các ổ cắm và các cạnh tạo thành một đồ thị có hướng không chu trình).
  • Ban đầu phích A cắm ở ổ thứ a, phích B cắm ở ổ thứ b, và tấm gỗ đã trải qua K bước trên trước khi trò chơi bắt đầu.
  • Hai người chơi luân phiên, Quang đi trước.
  • Ở mỗi lượt, người chơi chọn một trong ba hành động:
    • Chuyển phích A xuống một ổ mới: có thể chuyển A từ ổ u sang ổ v nếu có cạnh (u,v).
    • Chuyển phích B lên một ổ mới: có thể chuyển B từ ổ v sang ổ u nếu có cạnh (u,v).
    • Dùng máy C thực hiện một bước hợp lệ trên tấm gỗ (cắt hoặc ghép, tùy theo loại hai ổ đang cắm A và B).
  • Người không thể thực hiện một lượt hợp lệ sẽ thua.

Quang muốn biết mình có thắng được hay không, nếu cả hai đều chơi tối ưu. Hãy giúp anh ấy.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên T, số bộ dữ liệu. Mỗi bộ dữ liệu được mô tả như sau:

  • Dòng đầu chứa bốn số nguyên N,M,a,b (1≤a,b≤N≤105; 0≤M≤105).
  • Dòng thứ hai chứa một xâu độ dài N, ký tự thứ i là + hoặc - cho biết loại của ổ cắm thứ i.
  • M dòng tiếp theo, mỗi dòng chứa hai số nguyên u,v (1≤u,v≤N) cho biết có cạnh từ u đến v. Dữ liệu đảm bảo không có chu trình.
  • Dòng tiếp theo chứa ba số nguyên X,Y,K (0≤K≤105; 1≤X,Y≤105; X và Y là số lẻ).
  • Dòng thứ i trong K dòng tiếp theo chứa năm số nguyên t,u,v,p,q mô tả bước thứ i đã thực hiện trên tấm gỗ:
    • Nếu t=0 thì đây là một bước cắt, nếu t=1 thì đây là một bước ghép.
    • Các điểm nguyên trên tấm gỗ được đánh số từ (0,0) đến (X,Y). Máy cắt (hoặc ghép) theo đoạn thẳng từ điểm (u,v) đến điểm (p,q): với bước cắt, đó là đường cắt; với bước ghép, đó là cạnh chung của hai tấm anh em được ghép lại.
    • Dữ liệu đảm bảo đoạn từ (u,v) đến (p,q) song song với một cạnh của tấm gỗ và đây là một bước hợp lệ.

Tổng N, tổng M và tổng K trên tất cả các bộ dữ liệu đều không vượt quá 105.

Dữ liệu ra

In ra T dòng, dòng thứ i là YES nếu Quang thắng được trong bộ dữ liệu thứ i, ngược lại là NO.

Ràng buộc

  • 1≤a,b≤N≤105, 0≤M≤105.
  • 1≤X,Y≤105, X và Y là số lẻ; 0≤K≤105.
  • Tổng N, tổng M và tổng K trên tất cả các bộ dữ liệu không vượt quá 105.

Ví dụ

Input Output Giải thích
1
5 4 2 2
+-+-+
1 2
2 3
3 4
4 5
1 3 3
0 0 1 1 1
1 0 1 1 1
0 0 1 1 1
YES Tấm 1×3 được cắt ngang tại y=1, ghép lại rồi cắt lại, nên hiện có hai tấm anh em. Phích A còn đi được 3 bước (2→3→4→5), phích B còn đi được 1 bước (2→1).
2
3 2 1 1
++-
1 2
1 3
3 3 0
1 0 1 1
+
1 1 0
YES
NO
Bộ thứ hai: chỉ có một ổ, không có cạnh và tấm 1×1 không cắt được, nên Quang không có nước đi nào và thua.

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