結果

問題 No.1669 パズル作成
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:47:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,919 bytes
コンパイル時間 415 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 55,504 KB
最終ジャッジ日時 2025-05-14 12:48:51
合計ジャッジ時間 4,645 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1

    black = set()
    for _ in range(M):
        r = int(input[idx])-1; idx +=1
        c = int(input[idx])-1; idx +=1
        black.add((r, c))

    parent = list(range(2*N))

    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u

    def union(u, v):
        u = find(u)
        v = find(v)
        if u != v:
            parent[v] = u

    for r, c in black:
        union(r, N + c)

    component_map = {}
    components = []
    for i in range(2*N):
        root = find(i)
        if root not in component_map:
            component_map[root] = len(components)
            components.append([])
        components[component_map[root]].append(i)

    white_cells = defaultdict(int)
    total_white = 0
    for r in range(N):
        for c in range(N):
            if (r, c) not in black:
                total_white += 1
                root_r = find(r)
                root_c = find(N + c)
                white_cells[(root_r, root_c)] += 1

    comp_id = {}
    for i, comp in enumerate(components):
        for node in comp:
            comp_id[node] = i

    K = len(components)
    same_comp = [0]*K
    cross_comp = defaultdict(int)
    for (root_r, root_c), cnt in white_cells.items():
        i = comp_id[root_r]
        j = comp_id[root_c]
        if i == j:
            same_comp[i] += cnt
        else:
            if i > j:
                i, j = j, i
            cross_comp[(i, j)] += cnt

    dp = [defaultdict(lambda: float('inf')) for _ in range(K)]
    first_comp = 0
    dp[0][0] = same_comp[0]
    dp[0][1] = same_comp[0]

    for i in range(1, K):
        for prev_val in dp[i-1]:
            current_cost = dp[i-1][prev_val]
            for curr_val in [0, 1]:
                add = same_comp[i]
                for j in range(i):
                    pair = (j, i) if j < i else (i, j)
                    if pair in cross_comp:
                        if prev_val & (1 << j):
                            val_j = 1
                        else:
                            val_j = 0
                        if val_j == curr_val:
                            add += cross_comp[pair]
                new_val = prev_val | (curr_val << i)
                if dp[i][new_val] > current_cost + add:
                    dp[i][new_val] = current_cost + add
        if not dp[i]:
            min_prev = min(dp[i-1].values())
            dp[i][0] = min_prev + same_comp[i]
            dp[i][1 << i] = min_prev + same_comp[i]

    if K == 0:
        print(0)
        return

    min_total = min(dp[K-1].values())
    other_option = total_white
    print(min(min_total, other_option))

if __name__ == '__main__':
    main()
0