結果

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

ソースコード

diff # 

import sys

def readints():
    return list(map(int, sys.stdin.readline().split()))

def main():
    N, M = readints()
    edges = []
    for _ in range(M):
        a, b = readints()
        edges.append((a-1, b-1))  # 0-based
    c = readints()
    
    # Construct incidence matrix and augmented part
    rows = []
    for i in range(N):
        mask = 0
        for j in range(M):
            a, b = edges[j]
            if i == a or i == b:
                mask |= (1 << j)
        rows.append((mask, c[i]))
    
    # Perform Gaussian elimination over GF(2)
    rank = 0
    for col in range(M):
        # Find pivot
        pivot = -1
        for r in range(rank, N):
            if (rows[r][0] >> col) & 1:
                pivot = r
                break
        if pivot == -1:
            continue
        # Swap with current rank row
        rows[rank], rows[pivot] = rows[pivot], rows[rank]
        # Eliminate this column in lower rows
        for r in range(N):
            if r != rank and ((rows[r][0] >> col) & 1):
                rows[r] = (rows[r][0] ^ rows[rank][0], rows[r][1] ^ rows[rank][1])
        rank += 1
    
    # Check for contradictions
    for r in range(rank, N):
        if rows[r][1] == 1:
            print(-1)
            return
    
    # Find pivot columns
    pivot_cols = set()
    for r in range(rank):
        for c in range(M):
            if (rows[r][0] >> c) & 1:
                pivot_cols.add(c)
                break
    
    # Compute particular solution x_p
    x_p = [0] * M
    for r in reversed(range(rank)):
        mask, b = rows[r]
        if mask == 0:
            continue
        # Find pivot column
        pivot_col = -1
        for c in range(M):
            if (mask >> c) & 1:
                pivot_col = c
                break
        if pivot_col == -1:
            continue
        # Compute x_p[pivot_col]
        val = b
        for c_col in range(pivot_col + 1, M):
            if (mask >> c_col) & 1:
                val ^= x_p[c_col]
        x_p[pivot_col] = val
    
    # Find basis for homogeneous solutions
    free_vars = [c for c in range(M) if c not in pivot_cols]
    basis = []
    for j in free_vars:
        h = [0] * M
        h[j] = 1
        for r in reversed(range(rank)):
            mask, _ = rows[r]
            if mask == 0:
                continue
            # Find pivot column of this row
            pivot_col = -1
            for c in range(M):
                if (mask >> c) & 1:
                    pivot_col = c
                    break
            if pivot_col == -1:
                continue
            # Compute the value for pivot_col
            val = 0
            for c_col in range(pivot_col + 1, M):
                if (mask >> c_col) & 1:
                    val ^= h[c_col]
            h[pivot_col] = val
        basis.append(h)
    
    # Enumerate all possible combinations of basis vectors
    min_ops = None
    from itertools import product
    num_basis = len(basis)
    for bits in product([0,1], repeat=num_basis):
        h = [0] * M
        for i in range(num_basis):
            if bits[i]:
                for j in range(M):
                    h[j] ^= basis[i][j]
        # Compute x = x_p + h
        x = [ (x_p[j] + h[j]) % 2 for j in range(M) ]
        ops = sum(x)
        if min_ops is None or ops < min_ops:
            min_ops = ops
    
    print(min_ops if min_ops is not None else -1)

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