結果
問題 |
No.1669 パズル作成
|
ユーザー |
![]() |
提出日時 | 2025-06-12 17:05:59 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,649 bytes |
コンパイル時間 | 341 ms |
コンパイル使用メモリ | 82,272 KB |
実行使用メモリ | 89,864 KB |
最終ジャッジ日時 | 2025-06-12 17:06:04 |
合計ジャッジ時間 | 4,992 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | TLE * 1 -- * 28 |
ソースコード
import sys sys.setrecursionlimit(1 << 25) from collections import defaultdict def main(): import sys input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]); ptr +=1 M = int(input[ptr]); ptr +=1 A = [[0]* (N+1) for _ in range(N+1)] for _ in range(M): r = int(input[ptr]); ptr +=1 c = int(input[ptr]); ptr +=1 A[r][c] = 1 parent = {} def find(u): if parent[u] != u: parent[u] = find(parent[u]) return parent[u] def union(u, v): pu = find(u) pv = find(v) if pu != pv: parent[pu] = pv for r in range(1, N+1): for c in range(1, N+1): if A[r][c]: u = ('row', r) v = ('col', c) if u not in parent: parent[u] = u if v not in parent: parent[v] = v union(u, v) components = defaultdict(list) for u in parent: root = find(u) components[root].append(u) node_to_comp = {} for comp_id, comp in enumerate(components.values()): for u in comp: node_to_comp[u] = comp_id row_comp = {} col_comp = {} for u in parent: if u[0] == 'row': row_comp[u[1]] = node_to_comp[u] else: col_comp[u[1]] = node_to_comp[u] for i in range(1, N+1): if i not in row_comp: u = ('row', i) parent[u] = u node_to_comp[u] = len(components) row_comp[i] = len(components) components[len(components)] = [u] if i not in col_comp: u = ('col', i) parent[u] = u node_to_comp[u] = len(components) col_comp[i] = len(components) components[len(components)] = [u] adj = defaultdict(set) for r in range(1, N+1): for c in range(1, N+1): if A[r][c] == 0: cr = row_comp[r] cc = col_comp[c] adj[cr].add(cc) adj[cc].add(cr) from itertools import product comp_list = list(components.keys()) C = len(comp_list) min_total = float('inf') for mask in product([0,1], repeat=C): total = 0 for r in range(1, N+1): for c in range(1, N+1): if A[r][c] == 0: cr = row_comp[r] cc = col_comp[c] if mask[cr] == mask[cc]: total +=1 if total < min_total: min_total = total print(min_total) if __name__ == '__main__': main()