結果

問題 No.2236 Lights Out On Simple Graph
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:12:56
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,490 bytes
コンパイル時間 296 ms
コンパイル使用メモリ 82,000 KB
実行使用メモリ 66,720 KB
最終ジャッジ日時 2025-04-15 22:14:31
合計ジャッジ時間 6,952 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 TLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    edges = []
    for _ in range(M):
        a = int(input[idx]) - 1  # 0-based
        idx += 1
        b = int(input[idx]) - 1
        idx += 1
        edges.append((a, b))
    c = list(map(int, input[idx:idx+N]))
    idx += N
    c = [ci % 2 for ci in c]
    
    # Build the matrix rows and rhs
    rows = [0] * N
    for j in range(M):
        a, b = edges[j]
        rows[a] |= (1 << j)
        rows[b] |= (1 << j)
    rhs = c.copy()
    
    # Gaussian elimination over GF(2)
    rank = 0
    n = N
    m = M
    for col in range(m):
        # Find pivot
        pivot = -1
        for r in range(rank, n):
            if (rows[r] >> col) & 1:
                pivot = r
                break
        if pivot == -1:
            continue
        # Swap with rank-th row
        rows[rank], rows[pivot] = rows[pivot], rows[rank]
        rhs[rank], rhs[pivot] = rhs[pivot], rhs[rank]
        # Eliminate other rows
        for r in range(n):
            if r != rank and ((rows[r] >> col) & 1):
                rows[r] ^= rows[rank]
                rhs[r] ^= rhs[rank]
        rank += 1
    
    # Check for inconsistency
    for r in range(rank, n):
        if rhs[r] % 2 == 1:
            print(-1)
            return
    
    # Find pivot columns
    pivot_cols = []
    for r in range(rank):
        row = rows[r]
        col = 0
        while col < m and (row >> col) & 1 == 0:
            col += 1
        if col < m:
            pivot_cols.append(col)
    
    # Compute x0
    x0 = 0
    for r in reversed(range(rank)):
        row = rows[r]
        col = 0
        while col < m and (row >> col) & 1 == 0:
            col += 1
        if col >= m:
            continue
        sum_val = rhs[r] % 2
        for c in range(col + 1, m):
            if (row >> c) & 1:
                sum_val ^= (x0 >> c) & 1
        if sum_val:
            x0 |= (1 << col)
        else:
            x0 &= ~ (1 << col)
    
    # Find free variables
    free_vars = []
    for col in range(m):
        if col not in pivot_cols:
            free_vars.append(col)
    k = len(free_vars)
    
    # Compute basis vectors for null space
    basis = []
    for f in free_vars:
        vec = 0
        vec |= (1 << f)
        # Solve for pivot variables with rhs 0
        for r in reversed(range(rank)):
            row = rows[r]
            col_pivot = 0
            while col_pivot < m and (row >> col_pivot) & 1 == 0:
                col_pivot += 1
            if col_pivot >= m:
                continue
            sum_val = 0
            for c in range(col_pivot + 1, m):
                if (row >> c) & 1:
                    sum_val ^= (vec >> c) & 1
            if sum_val:
                vec |= (1 << col_pivot)
            else:
                vec &= ~ (1 << col_pivot)
        basis.append(vec)
    
    # Find minimal weight
    if not basis:
        min_ops = bin(x0).count('1')
    else:
        min_ops = float('inf')
        for mask in range(1 << len(basis)):
            current = 0
            for i in range(len(basis)):
                if (mask >> i) & 1:
                    current ^= basis[i]
            total = x0 ^ current
            cnt = bin(total).count('1')
            if cnt < min_ops:
                min_ops = cnt
    
    print(min_ops if min_ops != float('inf') else -1)

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