Trò Chơi Đồ Thị Grundy Phức Tạp
Points
65
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Đề bài
Cho đồ thị có hướng không chu trình (DAG) gồm n đỉnh và m cạnh. Có k đồng xu được đặt trên các đỉnh (có thể trùng nhau). Mỗi đỉnh có một trọng số w_i.
Hai người chơi thay phiên nhau. Mỗi lượt, người chơi phải:
- Chọn một đồng xu ở đỉnh u có ít nhất một cạnh đi ra.
- Di chuyển đồng xu đó dọc theo một cạnh từ u đến v.
- Ngoài ra, người chơi PHẢI đặt thêm w_v đồng xu mới lên đỉnh v (nếu w_v > 0).
Người chơi nào không thể di chuyển bất kỳ đồng xu nào sẽ thua.
Tuy nhiên, do đây là DAG và trọng số không âm, trò chơi luôn kết thúc.
Để đơn giản hóa, w_i ∈ {0, 1} cho tất cả đỉnh.
Người chơi đầu tiên đi trước. Xác định ai sẽ thắng nếu cả hai chơi tối ưu.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên n, m, k (1 ≤ n ≤ 2000, 0 ≤ m ≤ 5000, 1 ≤ k ≤ 10^5).
- Dòng thứ hai chứa n số nguyên w_1, w_2, ..., w_n (0 ≤ w_i ≤ 1).
- m dòng tiếp theo, mỗi dòng chứa hai số u, v (1 ≤ u, v ≤ n) — cạnh từ u đến v.
- Dòng cuối chứa k số nguyên v_1, v_2, ..., v_k — vị trí các đồng xu (có thể trùng).
- Đồ thị đảm bảo là DAG.
Dữ liệu ra
- In ra "First" nếu người chơi đầu tiên thắng, "Second" nếu người chơi thứ hai thắng.
Ví dụ
Input
3 2 1
0 0 0
1 2
2 3
1
Output
First
Giải thích
- Khi w_i = 0 cho tất cả, trò chơi giống Nim trên DAG thông thường.
- Đỉnh 1 → 2 → 3 (sink). Grundy(3)=0, Grundy(2)=1, Grundy(1)=mex{1}=0.
- Wait, Grundy(1)=0 → Second? Nhưng từ 1 đi đến 2, từ 2 đối thủ đi đến 3, rồi First kẹt? Không, từ 3 không đi được, nên người ở 3 thua.
- Đường: 1→2 (First), 2→3 (Second), 3 kẹt (First thua)? Hmm, di chuyển: First di 1→2, Second di 2→3, First không di được → First thua. Grundy(1)=0 đúng → Second thắng?
- Nhưng kết quả là First. Hãy kiểm tra: chỉ có 1 đồng xu ở đỉnh 1. Grundy(1)=0, XOR=0 → Second thắng.
Input chỉnh lại
3 2 1
0 0 0
1 2
2 3
2
Output
First
Giải thích
- Đồng xu ở đỉnh 2, Grundy(2) = mex{Grundy(3)} = mex{0} = 1 ≠ 0 → First thắng.
Giới hạn
- 1 ≤ n ≤ 2000
- 0 ≤ m ≤ 5000
- 1 ≤ k ≤ 10^5
- 0 ≤ w_i ≤ 1
- Đồ thị là DAG
- Thời gian: 3 giây
- Bộ nhớ: 256 MB
Community Discussion