結果

問題 No.2236 Lights Out On Simple Graph
コンテスト
ユーザー aaaaaaaaaa2230
提出日時 2023-03-03 23:19:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,287 ms / 4,000 ms
コード長 886 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,588 KB
実行使用メモリ 176,412 KB
最終ジャッジ日時 2024-09-18 00:27:38
合計ジャッジ時間 38,646 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,m = map(int,input().split())
AB = [[int(x)-1 for x in input().split()] for i in range(m)]
C = list(map(int,input().split()))

ans = m+1

dic = {}
l,r = AB[:m//2],AB[m//2:]
# print(l)
# print(r)
base = 0
for c in C[::-1]:
    base <<= 1
    base |= c
# print(base)
ll = len(l)
for b in range(1<<ll):

    num = base
    count = 0
    for i,(x,y) in enumerate(l):
        if b >> i & 1:
            count += 1
            num ^= 1<<x
            num ^= 1<<y
    # print(num,count)
    if num in dic:
        dic[num] = min(dic[num],count)
    else:
        dic[num] = count

lr = len(r)
for b in range(1<<lr):
    
    num = 0
    count = 0
    for i,(x,y) in enumerate(r):
        if b >> i & 1:
            count += 1
            num ^= 1<<x
            num ^= 1<<y
    # print(num,count)
    if num in dic:
        ans = min(ans,count+dic[num])
if ans == m+1:
    ans = -1
print(ans)
0