結果

問題 No.2236 Lights Out On Simple Graph
ユーザー gew1fw
提出日時 2025-06-12 18:23:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,020 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 83,988 KB
最終ジャッジ日時 2025-06-12 18:24:32
合計ジャッジ時間 8,603 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48 WA * 8 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import product

def main():
    N, M = map(int, sys.stdin.readline().split())
    edges = []
    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        edges.append((a-1, b-1))  # Convert to 0-based vertices

    c = list(map(int, sys.stdin.readline().split()))
    rows = []
    for i in range(N):
        mask = 0
        for j, (a, b) in enumerate(edges):
            if i == a or i == b:
                mask |= 1 << j
        rhs = c[i]
        rows.append((mask, rhs))

    # Perform Gaussian elimination over GF(2)
    current_pivot = 0
    for col in range(M):
        # Find the pivot row
        pivot_row = None
        for r in range(current_pivot, N):
            if (rows[r][0] & (1 << col)) != 0:
                pivot_row = r
                break
        if pivot_row is None:
            continue
        # Swap with current_pivot row
        rows[current_pivot], rows[pivot_row] = rows[pivot_row], rows[current_pivot]
        # Eliminate this column in rows below
        for r in range(current_pivot + 1, N):
            if (rows[r][0] & (1 << col)) != 0:
                rows[r] = (rows[r][0] ^ rows[current_pivot][0], rows[r][1] ^ rows[current_pivot][1])
        current_pivot += 1

    # Check for inconsistency (0x = 1)
    for mask, rhs in rows:
        if mask == 0 and rhs == 1:
            print(-1)
            return

    # Collect pivot columns and free variables
    pivot_cols = []
    row_pivots = []
    for r in range(N):
        mask, rhs = rows[r]
        if mask == 0:
            continue
        for col in range(M):
            if (mask & (1 << col)) != 0:
                pivot_cols.append(col)
                row_pivots.append((r, col))
                break

    free_vars = [col for col in range(M) if col not in pivot_cols]
    k = len(free_vars)
    if k > 20:
        print(-1)
        return

    # Prepare rows sorted by pivot column in reverse order
    sorted_rows = []
    for r in range(N):
        mask, rhs = rows[r]
        if mask == 0:
            continue
        for col in range(M):
            if (mask & (1 << col)) != 0:
                pivot_col = col
                break
        sorted_rows.append((pivot_col, mask, rhs))
    sorted_rows.sort(reverse=True, key=lambda x: x[0])

    min_ops = float('inf')
    for bits in product([0, 1], repeat=k):
        solution = [0] * M
        for i in range(k):
            solution[free_vars[i]] = bits[i]
        # Compute pivot variables
        for pivot_col, mask, rhs in sorted_rows:
            sum_val = 0
            for j in range(M):
                if j == pivot_col:
                    continue
                if (mask & (1 << j)) != 0:
                    sum_val ^= solution[j]
            solution[pivot_col] = (rhs ^ sum_val) & 1
        total = sum(solution)
        if total < min_ops:
            min_ops = total

    if min_ops == float('inf'):
        print(-1)
    else:
        print(min_ops)

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