結果

問題 No.1669 パズル作成
コンテスト
ユーザー gew1fw
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0