結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, sys.stdin.readline().split())
    b = [[0 for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        r, c = map(int, sys.stdin.readline().split())
        r -= 1
        c -= 1
        b[r][c] = 1

    # Total nodes: rows (0..N-1) and columns (N..2N-1)
    visited = [False] * (2 * N)
    total_flips = 0

    for node in range(2 * N):
        if not visited[node]:
            # Try both possible starting colors
            min_flips = float('inf')
            for start_color in [0, 1]:
                color = [None] * (2 * N)
                queue = deque()
                queue.append(node)
                color[node] = start_color
                valid = True
                flips = 0

                while queue:
                    u = queue.popleft()
                    if u < N:
                        # It's a row node
                        for j in range(N):
                            s = 1 - b[u][j]
                            v = N + j
                            expected_color = (color[u] + s) % 2
                            if color[v] is None:
                                color[v] = expected_color
                                queue.append(v)
                            else:
                                if color[v] != expected_color:
                                    valid = False
                                    break
                        if not valid:
                            break
                    else:
                        # It's a column node
                        j = u - N
                        for i in range(N):
                            s = 1 - b[i][j]
                            v = i
                            expected_color = (color[u] + s) % 2
                            if color[v] is None:
                                color[v] = expected_color
                                queue.append(v)
                            else:
                                if color[v] != expected_color:
                                    valid = False
                                    break
                        if not valid:
                            break
                if valid:
                    # Now count the flips needed
                    current_flips = 0
                    for i in range(N):
                        for j in range(N):
                            s = 1 - b[i][j]
                            a = color[i]
                            c_col = color[N + j]
                            if (a + c_col) % 2 != s:
                                current_flips += 1
                    if current_flips < min_flips:
                        min_flips = current_flips
            total_flips += min_flips
            # Mark all nodes in this component as visited
            queue = deque()
            queue.append(node)
            visited[node] = True
            while queue:
                u = queue.popleft()
                if u < N:
                    for j in range(N):
                        v = N + j
                        if not visited[v]:
                            visited[v] = True
                            queue.append(v)
                else:
                    j = u - N
                    for i in range(N):
                        v = i
                        if not visited[v]:
                            visited[v] = True
                            queue.append(v)
    print(total_flips)

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