結果

問題 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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0