結果

問題 No.2236 Lights Out On Simple Graph
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:04:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,028 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 82,840 KB
実行使用メモリ 84,060 KB
最終ジャッジ日時 2025-06-12 14:04:52
合計ジャッジ時間 6,377 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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
        idx += 1
        b = int(input[idx]) - 1
        idx += 1
        edges.append((a, b))

    c = list(map(int, input[idx:idx+N]))
    idx += N

    # Check if sum(c) is even
    sum_c = sum(c)
    if sum_c % 2 != 0:
        print(-1)
        return

    # Construct the matrix
    matrix = [0] * N
    for i in range(N):
        matrix[i] = (c[i] << M)  # Augmented part is in the M-th bit

    for edge_idx, (a, b) in enumerate(edges):
        # Set the bits for a and b
        matrix[a] |= (1 << edge_idx)
        matrix[b] |= (1 << edge_idx)

    # Perform Gaussian elimination over GF(2)
    rank = 0
    for col in range(M):
        pivot_row = None
        for r in range(rank, N):
            if (matrix[r] >> col) & 1:
                pivot_row = r
                break
        if pivot_row is None:
            continue
        matrix[rank], matrix[pivot_row] = matrix[pivot_row], matrix[rank]
        for r in range(N):
            if r != rank and ((matrix[r] >> col) & 1):
                matrix[r] ^= matrix[rank]
        rank += 1

    # Check for inconsistency
    for row in matrix:
        coeff = row & ((1 << M) - 1)
        if coeff == 0 and (row >> M) & 1:
            print(-1)
            return

    # Identify pivot columns
    pivots = set()
    for r in range(rank):
        for c in range(M):
            if (matrix[r] >> c) & 1:
                pivots.add(c)
                break

    # Find x0
    x0 = 0
    for r in range(rank):
        for c in range(M):
            if (matrix[r] >> c) & 1:
                x0 ^= (( (matrix[r] >> M) & 1 ) << c)
                break

    # Find basis for homogeneous solutions
    basis = []
    free_cols = [c for c in range(M) if c not in pivots]
    for f in free_cols:
        x = 1 << f
        for r in reversed(range(rank)):
            row = matrix[r]
            pivot_col = None
            for c in range(M):
                if (row >> c) & 1:
                    pivot_col = c
                    break
            if pivot_col is None:
                continue
            sum_val = 0
            for c in range(M):
                if c == pivot_col:
                    continue
                if (row >> c) & 1:
                    if (x >> c) & 1:
                        sum_val ^= 1
            x ^= (sum_val << pivot_col)
        basis.append(x)

    # Generate all possible combinations of the basis vectors
    k = len(basis)
    min_weight = float('inf')
    for mask in range(1 << k):
        current = x0
        for i in range(k):
            if (mask >> i) & 1:
                current ^= basis[i]
        weight = bin(current).count('1')
        if weight < min_weight:
            min_weight = weight

    print(min_weight if min_weight != float('inf') else -1)

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