結果

問題 No.2236 Lights Out On Simple Graph
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:13:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,741 bytes
コンパイル時間 409 ms
コンパイル使用メモリ 81,912 KB
実行使用メモリ 69,004 KB
最終ジャッジ日時 2025-04-15 22:14:33
合計ジャッジ時間 6,690 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
        idx += 1
        edges.append((a, b))

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

    # Build the system of equations
    matrix = []
    for i in range(N):
        mask = 0
        for j in range(M):
            a, b = edges[j]
            if a == i or b == i:
                mask |= 1 << j
        val = c[i]
        matrix.append((mask, val))

    # Gaussian elimination over GF(2)
    pivot_row = 0
    pivot_cols = []
    n = N  # number of rows
    m = M  # number of variables (edges)
    for col in range(m):
        # Find pivot in column 'col' starting from pivot_row
        pivot = -1
        for r in range(pivot_row, n):
            if (matrix[r][0] & (1 << col)) != 0:
                pivot = r
                break
        if pivot == -1:
            continue  # free variable
        # Swap with pivot_row
        matrix[pivot_row], matrix[pivot] = matrix[pivot], matrix[pivot_row]
        # Eliminate this column in other rows
        for r in range(n):
            if r != pivot_row and (matrix[r][0] & (1 << col)) != 0:
                matrix[r] = (matrix[r][0] ^ matrix[pivot_row][0], matrix[r][1] ^ matrix[pivot_row][1])
        pivot_cols.append(col)
        pivot_row += 1

    # Check for inconsistency (0x = 1)
    has_inconsistent = False
    for r in range(pivot_row, n):
        if matrix[r][1] != 0:
            has_inconsistent = True
            break
    if has_inconsistent:
        print(-1)
        return

    # Build particular solution
    x_p = 0
    for r in range(pivot_row):
        row_mask, row_val = matrix[r]
        # Find pivot column
        pivot_col = -1
        for c in range(m):
            if (row_mask & (1 << c)) != 0:
                pivot_col = c
                break
        if row_val:
            x_p |= 1 << pivot_col

    # Collect free variables (columns not in pivot_cols)
    free_vars = []
    for col in range(m):
        if col not in pivot_cols:
            free_vars.append(col)

    # Build null space basis vectors
    basis = []
    for f in free_vars:
        vec = 1 << f
        # Solve for leading variables in homogeneous system
        for r in range(pivot_row):
            row_mask, row_val = matrix[r]
            # Find pivot column for this row
            pivot_col = -1
            for c in range(m):
                if (row_mask & (1 << c)) != 0:
                    pivot_col = c
                    break
            if pivot_col == -1:
                continue
            # Compute sum of variables in this row except pivot_col
            sum_val = 0
            for c in range(m):
                if c == pivot_col:
                    continue
                if (row_mask & (1 << c)) != 0 and (vec & (1 << c)) != 0:
                    sum_val ^= 1
            # Set pivot_col in vec based on sum_val
            if sum_val:
                vec |= 1 << pivot_col
            else:
                vec &= ~(1 << pivot_col)
        basis.append(vec)

    # Find minimal operations by trying all combinations of basis vectors
    min_ops = bin(x_p).count('1')  # initial solution
    k = len(basis)
    for mask in range(1 << k):
        current = 0
        for i in range(k):
            if (mask >> i) & 1:
                current ^= basis[i]
        candidate = x_p ^ current
        cnt = bin(candidate).count('1')
        if cnt < min_ops:
            min_ops = cnt
    print(min_ops)

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