結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    index = 0
    N = int(data[index])
    index += 1
    M = int(data[index])
    index += 1
    
    edges = []
    for _ in range(M):
        a = int(data[index]) - 1  # convert to 0-based
        index += 1
        b = int(data[index]) - 1
        index += 1
        edges.append((a, b))
    
    c = list(map(int, data[index:index + N]))
    index += N

    # Create equations: each row is (mask, target)
    rows = []
    for i in range(N):
        mask = 0
        for j in range(M):
            a, b = edges[j]
            if i == a or i == b:
                mask |= (1 << j)
        target = c[i]
        rows.append((mask, target))

    rank = 0
    pivot_cols = []  # list of pivot columns (variable indices)
    n = N

    # Gaussian elimination
    for col in range(M):  # columns are processed from 0 to M-1 (left to right)
        pivot_row = -1
        for r in range(rank, n):
            if (rows[r][0] >> col) & 1:
                pivot_row = r
                break
        if pivot_row == -1:
            continue

        # Swap current row (rank) with pivot_row
        rows[rank], rows[pivot_row] = rows[pivot_row], rows[rank]
        current_row = rows[rank]

        # Eliminate this column in other rows
        for r in range(n):
            if r != rank and ( (rows[r][0] >> col) & 1 ):
                # XOR with current_row
                rows[r] = (rows[r][0] ^ current_row[0], rows[r][1] ^ current_row[1])

        pivot_cols.append(col)
        rank += 1

    # Check for inconsistency (0 = 1)
    for r in range(rank, n):
        if rows[r][1] != 0:
            print(-1)
            return

    # If no equations, check if all targets are zero (trivial solution)
    if rank == 0:
        for t in [row[1] for row in rows]:
            if t != 0:
                print(-1)
                return
        print(0)
        return

    # Now, find solutions
    pivot_set = set(pivot_cols)
    free_vars = [col for col in range(M) if col not in pivot_set]
    k = len(free_vars)

    min_ops = float('inf')

    from itertools import product

    # Generate all possible combinations of free variables (0/1)
    for bits in product([0, 1], repeat=k):
        x = [0] * M

        # Assign values to free variables
        for i in range(k):
            x[free_vars[i]] = bits[i]

        # Compute pivot variables from highest to lowest column (reverse order of pivot_cols)
        for r in reversed(range(rank)):
            col = pivot_cols[r]
            mask, target = rows[r]
            sum_val = 0
            for j in range(M):
                if j == col:
                    continue
                if (mask >> j) & 1:
                    sum_val ^= x[j]
            x[col] = (target ^ sum_val) & 1

        # Calculate the number of operations
        total = sum(x)
        if total < min_ops:
            min_ops = total

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

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