結果

問題 No.2236 Lights Out On Simple Graph
ユーザー lam6er
提出日時 2025-04-15 22:13:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,538 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 81,588 KB
実行使用メモリ 72,740 KB
最終ジャッジ日時 2025-04-15 22:14:38
合計ジャッジ時間 6,331 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  # converting to 0-based
        idx += 1
        b = int(input[idx]) - 1  # converting to 0-based
        idx += 1
        edges.append((a, b))
    c = list(map(int, input[idx:idx+N]))
    idx += N

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

    # Build the augmented matrix
    matrix = []
    for v in range(N):
        row = [0] * (M + 1)
        # Vertex v (0-based) corresponds to original vertex v+1
        for i, (a, b) in enumerate(edges):
            if a == v or b == v:
                row[i] = 1
        row[M] = c[v]
        matrix.append(row)

    # Perform Gaussian elimination over GF(2)
    current_row = 0
    for col in range(M):
        # Find pivot row
        pivot_row = None
        for r in range(current_row, len(matrix)):
            if matrix[r][col] == 1:
                pivot_row = r
                break
        if pivot_row is None:
            continue
        # Swap with current_row
        matrix[current_row], matrix[pivot_row] = matrix[pivot_row], matrix[current_row]
        # Eliminate all other rows
        for r in range(len(matrix)):
            if r != current_row and matrix[r][col] == 1:
                for k in range(col, M + 1):
                    matrix[r][k] ^= matrix[current_row][k]
        current_row += 1
        if current_row >= len(matrix):
            break

    # Check for inconsistency
    for row in matrix:
        all_zero = True
        for col in range(M):
            if row[col] != 0:
                all_zero = False
                break
        if all_zero and row[M] == 1:
            print(-1)
            return

    # Collect pivot rows and their leading columns
    pivot_cols = set()
    rows_reduced = []
    for row in matrix:
        leading_col = None
        for col in range(M):
            if row[col] == 1:
                leading_col = col
                break
        if leading_col is not None:
            pivot_cols.add(leading_col)
            rows_reduced.append((leading_col, row))

    # Reverse the rows to process from highest leading_col to lowest
    reversed_rows_reduced = list(reversed(rows_reduced))
    free_cols = [col for col in range(M) if col not in pivot_cols]
    num_free = len(free_cols)

    if num_free == 0:
        # Only one possible solution
        x = [0] * M
        for leading_col, row in reversed_rows_reduced:
            sum_val = row[M]
            for k in range(leading_col + 1, M):
                if row[k]:
                    sum_val ^= x[k]
            x[leading_col] = sum_val
        print(sum(x))
        return

    min_ops = float('inf')
    from itertools import product

    for bits in product([0, 1], repeat=num_free):
        x = [0] * M
        # Assign free variables
        for i in range(num_free):
            x[free_cols[i]] = bits[i]
        # Process each row in reversed order
        for leading_col, row in reversed_rows_reduced:
            sum_val = row[M]
            for k in range(leading_col + 1, M):
                if row[k]:
                    sum_val ^= x[k]
            x[leading_col] = 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