結果

問題 No.2236 Lights Out On Simple Graph
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:43:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,927 bytes
コンパイル時間 392 ms
コンパイル使用メモリ 81,980 KB
実行使用メモリ 83,768 KB
最終ジャッジ日時 2025-04-16 15:46:47
合計ジャッジ時間 7,083 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

    total_c = sum(c)
    if total_c % 2 != 0:
        print(-1)
        return

    # Build the matrix
    matrix = [[0] * (M + 1) for _ in range(N)]
    for i in range(N):
        for j in range(M):
            a, b = edges[j]
            if i == a or i == b:
                matrix[i][j] = 1
        matrix[i][M] = c[i]

    # Gaussian elimination over GF(2)
    pivots = []
    rank = 0
    for col in range(M):
        # Find pivot row
        pivot_row = -1
        for r in range(rank, N):
            if matrix[r][col]:
                pivot_row = r
                break
        if pivot_row == -1:
            continue

        # Swap with the current rank row
        matrix[rank], matrix[pivot_row] = matrix[pivot_row], matrix[rank]

        # Eliminate this column in all other rows
        for r in range(N):
            if r != rank and matrix[r][col]:
                for c_col in range(col, M + 1):
                    matrix[r][c_col] ^= matrix[rank][c_col]

        pivots.append(col)
        rank += 1

    # Check for inconsistency
    for row in range(rank, N):
        if matrix[row][M]:
            print(-1)
            return

    # Collect free columns
    free_cols = []
    for col in range(M):
        if col not in pivots:
            free_cols.append(col)
    k = len(free_cols)

    min_ops = float('inf')

    if k == 0:
        # No free variables, compute the solution
        x = [0] * M
        for i in reversed(range(len(pivots))):
            row = i
            pivot_col = pivots[i]
            sum_val = 0
            for c_col in range(pivot_col + 1, M):
                sum_val ^= matrix[row][c_col] * x[c_col]
            x[pivot_col] = matrix[row][M] ^ sum_val
        min_ops = sum(x)
    else:
        # Iterate over all possible masks for free variables
        for mask in range(0, 1 << k):
            x = [0] * M
            for i in range(k):
                if (mask >> i) & 1:
                    x[free_cols[i]] = 1

            # Compute pivot variables in reverse order
            for i in reversed(range(len(pivots))):
                row = i
                pivot_col = pivots[i]
                sum_val = 0
                for c_col in range(pivot_col + 1, M):
                    sum_val ^= matrix[row][c_col] * x[c_col]
                x[pivot_col] = matrix[row][M] ^ sum_val

            total = sum(x)
            if total < min_ops:
                min_ops = total

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

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