結果

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

ソースコード

diff #
プレゼンテーションモードにする

def main():
    import sys
    N, M = map(int, sys.stdin.readline().split())
    edges = []
    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        edges.append((a-1, b-1))  # 0-based
    
    c = list(map(int, sys.stdin.readline().split()))
    
    # Create matrix
    matrix = []
    for i in range(N):
        row = 0
        # Set edge bits
        for j in range(M):
            a, b = edges[j]
            if a == i or b == i:
                row |= 1 << j
        # Set right-hand side (bit M)
        if c[i]:
            row |= 1 << M
        matrix.append(row)
    
    # Gaussian elimination
    rank = 0
    pivot_cols = []  # List of (row index, col)
    for col in range(M):
        # Find pivot row
        pivot = -1
        for r in range(rank, N):
            if (matrix[r] & (1 << col)) != 0:
                pivot = r
                break
        if pivot == -1:
            continue
        # Swap with the current rank row
        matrix[rank], matrix[pivot] = matrix[pivot], matrix[rank]
        # Eliminate this column in other rows
        for r in range(N):
            if r != rank and (matrix[r] & (1 << col)):
                matrix[r] ^= matrix[rank]
        pivot_cols.append( (rank, col) )
        rank += 1
    
    # Check for no solution
    for r in range(N):
        lhs = matrix[r] & ((1 << M) -1)
        rhs = (matrix[r] >> M) & 1
        if lhs == 0 and rhs == 1:
            print(-1)
            return
    
    # Determine free columns and pivot info
    used_cols = set(col for _, col in pivot_cols)
    free_cols = [col for col in range(M) if col not in used_cols]
    # Collect the pivot rows and their columns, and original row data
    pivot_info = []
    for r in range(N):
        row = matrix[r]
        lhs = row & ((1 << M) -1)
        if lhs == 0:
            continue
        for col in range(M):
            if (row >> col) & 1:
                pivot_col = col
                break
        pivot_info.append( (r, row, pivot_col) )
    
    min_ops = None
    # Iterate over all possible free variables assignments (0/1)
    from itertools import product
    for bits in product([0,1], repeat=len(free_cols)):
        x = [0]*M
        # Assign free variables
        for i in range(len(free_cols)):
            x[free_cols[i]] = bits[i]
        # Assign pivot variables
        # Process pivot rows in reverse order
        for info in reversed(pivot_info):
            r, row, col = info
            rhs = (row >> M) & 1
            val = rhs
            # XOR with the other variables in the row
            for c in range(col+1, M):
                if (row >> c) & 1:
                    val ^= x[c]
            x[col] = val
        # Calculate total operations
        total = sum(x)
        if min_ops is None or total < min_ops:
            min_ops = total
    
    if min_ops is not None:
        print(min_ops)
    else:
        print(-1)
    
if __name__ == "__main__":
    main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0