結果

問題 No.2236 Lights Out On Simple Graph
ユーザー roaris
提出日時 2023-03-04 00:50:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,852 ms / 4,000 ms
コード長 890 bytes
コンパイル時間 279 ms
コンパイル使用メモリ 82,196 KB
実行使用メモリ 259,336 KB
最終ジャッジ日時 2024-09-18 00:49:27
合計ジャッジ時間 51,285 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
from collections import *

N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
c = list(map(int, input().split()))
M1 = M//2
M2 = M-M1
pair = defaultdict(lambda: 10**18)

for S in range(1<<M1):
    mask = 0
    cnt = 0
    
    for i in range(M1):
        if (S>>i)&1:
            u, v = edges[i]
            mask ^= 1<<(u-1)
            mask ^= 1<<(v-1)
            cnt += 1
    
    for v in range(N):
        if c[v]==1:
            mask ^= 1<<v
    
    pair[mask] = min(pair[mask], cnt)

ans = 10**18

for S in range(1<<M2):
    mask = 0
    cnt = 0
    
    for i in range(M2):
        if (S>>i)&1:
            u, v = edges[M1+i]
            mask ^= 1<<(u-1)
            mask ^= 1<<(v-1)
            cnt += 1

    ans = min(ans, cnt+pair[mask])
        
if ans==10**18:
    print(-1)
else:
    print(ans)
0