結果
問題 |
No.1669 パズル作成
|
ユーザー |
![]() |
提出日時 | 2025-04-24 12:21:53 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,919 bytes |
コンパイル時間 | 223 ms |
コンパイル使用メモリ | 82,388 KB |
実行使用メモリ | 63,044 KB |
最終ジャッジ日時 | 2025-04-24 12:23:43 |
合計ジャッジ時間 | 3,828 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | TLE * 1 -- * 28 |
ソースコード
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()