結果
問題 |
No.1669 パズル作成
|
ユーザー |
![]() |
提出日時 | 2025-06-12 17:06:40 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,595 bytes |
コンパイル時間 | 213 ms |
コンパイル使用メモリ | 82,244 KB |
実行使用メモリ | 281,568 KB |
最終ジャッジ日時 | 2025-06-12 17:06:46 |
合計ジャッジ時間 | 4,816 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 2 WA * 2 TLE * 1 -- * 24 |
ソースコード
import sys from collections import deque def main(): sys.setrecursionlimit(1 << 25) N, M = map(int, sys.stdin.readline().split()) b = [[0 for _ in range(N)] for _ in range(N)] for _ in range(M): r, c = map(int, sys.stdin.readline().split()) r -= 1 c -= 1 b[r][c] = 1 # Total nodes: rows (0..N-1) and columns (N..2N-1) visited = [False] * (2 * N) total_flips = 0 for node in range(2 * N): if not visited[node]: # Try both possible starting colors min_flips = float('inf') for start_color in [0, 1]: color = [None] * (2 * N) queue = deque() queue.append(node) color[node] = start_color valid = True flips = 0 while queue: u = queue.popleft() if u < N: # It's a row node for j in range(N): s = 1 - b[u][j] v = N + j expected_color = (color[u] + s) % 2 if color[v] is None: color[v] = expected_color queue.append(v) else: if color[v] != expected_color: valid = False break if not valid: break else: # It's a column node j = u - N for i in range(N): s = 1 - b[i][j] v = i expected_color = (color[u] + s) % 2 if color[v] is None: color[v] = expected_color queue.append(v) else: if color[v] != expected_color: valid = False break if not valid: break if valid: # Now count the flips needed current_flips = 0 for i in range(N): for j in range(N): s = 1 - b[i][j] a = color[i] c_col = color[N + j] if (a + c_col) % 2 != s: current_flips += 1 if current_flips < min_flips: min_flips = current_flips total_flips += min_flips # Mark all nodes in this component as visited queue = deque() queue.append(node) visited[node] = True while queue: u = queue.popleft() if u < N: for j in range(N): v = N + j if not visited[v]: visited[v] = True queue.append(v) else: j = u - N for i in range(N): v = i if not visited[v]: visited[v] = True queue.append(v) print(total_flips) if __name__ == "__main__": main()