結果
問題 |
No.1669 パズル作成
|
ユーザー |
![]() |
提出日時 | 2025-06-12 17:06:56 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,671 bytes |
コンパイル時間 | 397 ms |
コンパイル使用メモリ | 82,024 KB |
実行使用メモリ | 100,020 KB |
最終ジャッジ日時 | 2025-06-12 17:07:04 |
合計ジャッジ時間 | 5,620 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 3 WA * 2 TLE * 1 -- * 23 |
ソースコード
import sys from collections import defaultdict def main(): N, M = map(int, sys.stdin.readline().split()) initial_black = set() for _ in range(M): r, c = map(int, sys.stdin.readline().split()) initial_black.add((r-1, c-1)) # converting to 0-based min_x = float('inf') for T_11 in [0, 1]: parent = {} rank = {} parity = {} def find(u): if u not in parent: parent[u] = u rank[u] = 1 parity[u] = 0 if parent[u] != u: orig_parent = parent[u] parent[u] = find(parent[u])[0] parity[u] ^= parity[orig_parent] return parent[u], parity[u] def union(u, v, b): u_root, u_par = find(u) v_root, v_par = find(v) if u_root == v_root: if (u_par ^ v_par) != b: return False # contradiction else: return True if rank[u_root] < rank[v_root]: parent[u_root] = v_root parity[u_root] = u_par ^ v_par ^ b else: parent[v_root] = u_root parity[v_root] = u_par ^ v_par ^ b if rank[u_root] == rank[v_root]: rank[u_root] += 1 return True consistent = True rows = set() cols = set() for (i, j) in initial_black: u = i v = N + j rows.add(u) cols.add(v) if not union(u, v, T_11): consistent = False break if not consistent: continue R = {} C = {} for u in parent: root, p = find(u) if u < N: R[u] = p else: C[u - N] = p for i in range(N): if i not in R: R[i] = 0 for j in range(N): if j not in C: C[j] = 0 x_count = 0 valid = True for (i, j) in initial_black: T = R[i] ^ C[j] ^ T_11 if T != 0: valid = False break if not valid: continue for i in range(N): for j in range(N): if (i, j) not in initial_black: T = R[i] ^ C[j] ^ T_11 if T == 0: x_count += 1 if x_count < min_x: min_x = x_count if min_x == float('inf'): print(0) else: print(min_x) if __name__ == '__main__': main()