結果

問題 No.2236 Lights Out On Simple Graph
ユーザー gew1fw
提出日時 2025-06-12 13:59:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,943 ms / 4,000 ms
コード長 3,872 bytes
コンパイル時間 352 ms
コンパイル使用メモリ 82,800 KB
実行使用メモリ 282,036 KB
最終ジャッジ日時 2025-06-12 14:01:49
合計ジャッジ時間 77,175 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    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))  # zero-based
    c = list(map(int, sys.stdin.readline().split()))
    
    # Function to find connected components
    def find_components():
        visited = [False] * N
        components = []
        for i in range(N):
            if not visited[i]:
                q = deque()
                q.append(i)
                visited[i] = True
                component = []
                while q:
                    u = q.popleft()
                    component.append(u)
                    for v in range(N):
                        if (u, v) in edge_set or (v, u) in edge_set:
                            if not visited[v]:
                                visited[v] = True
                                q.append(v)
                components.append(component)
        return components
    
    edge_set = set(edges)
    components = find_components()
    
    total = 0
    for comp in components:
        k = len(comp)
        # Create a mapping from vertex to index in the component
        vertex_index = {u: i for i, u in enumerate(comp)}
        # Extract edges in this component
        edges_in_comp = []
        for a, b in edges:
            if a in comp and b in comp:
                edges_in_comp.append((a, b))
        m = len(edges_in_comp)
        # Compute sum of c_v for the component
        sum_c = sum(c[u] for u in comp)
        if sum_c % 2 != 0:
            print(-1)
            return
        # Now, split edges into two halves
        if m == 0:
            # No edges, so if sum_c is 0, nothing to do. Otherwise, impossible.
            if sum(c[u] for u in comp) != 0:
                print(-1)
                return
            continue
        # Split into two halves
        half = m // 2
        A_edges = edges_in_comp[:half]
        B_edges = edges_in_comp[half:]
        # Precompute all subset vectors for A
        A_size = len(A_edges)
        A_vectors = {}
        # Generate all subsets of A_edges
        for mask in range(0, 1 << A_size):
            bits = bin(mask).count('1')
            vec = 0
            for i in range(A_size):
                if (mask >> i) & 1:
                    a, b = A_edges[i]
                    ai = vertex_index[a]
                    bi = vertex_index[b]
                    vec ^= (1 << ai) | (1 << bi)
            if vec not in A_vectors or bits < A_vectors[vec]:
                A_vectors[vec] = bits
        # Precompute all subset vectors for B
        B_size = len(B_edges)
        B_vectors = {}
        for mask in range(0, 1 << B_size):
            bits = bin(mask).count('1')
            vec = 0
            for i in range(B_size):
                if (mask >> i) & 1:
                    a, b = B_edges[i]
                    ai = vertex_index[a]
                    bi = vertex_index[b]
                    vec ^= (1 << ai) | (1 << bi)
            if vec not in B_vectors or bits < B_vectors[vec]:
                B_vectors[vec] = bits
        # Now, compute the target vector
        target = 0
        for u in comp:
            if c[u] == 1:
                i = vertex_index[u]
                target ^= (1 << i)
        min_edges = float('inf')
        # Try all possible vectors from A
        for vec_A in A_vectors:
            need = target ^ vec_A
            if need in B_vectors:
                total_edges = A_vectors[vec_A] + B_vectors[need]
                if total_edges < min_edges:
                    min_edges = total_edges
        if min_edges == float('inf'):
            print(-1)
            return
        total += min_edges
    print(total)

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