結果
問題 |
No.2236 Lights Out On Simple Graph
|
ユーザー |
![]() |
提出日時 | 2023-12-01 02:33:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,197 ms / 4,000 ms |
コード長 | 745 bytes |
コンパイル時間 | 405 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 273,964 KB |
最終ジャッジ日時 | 2024-09-26 15:08:07 |
合計ジャッジ時間 | 31,433 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
import sys readline=sys.stdin.readline from collections import defaultdict N,M=map(int,readline().split()) A,B=[],[] for m in range(M): a,b=map(int,readline().split()) a-=1;b-=1 A.append(a) B.append(b) inf=1<<60 m=M//2 dct=defaultdict(lambda:inf) for bit in range(1<<m): c=0 for i in range(m): if bit&1<<i: c^=1<<A[i] c^=1<<B[i] dct[c]=min(dct[c],sum(1 for i in range(m) if bit&1<<i)) C=sum(c<<i for i,c in enumerate(map(int,readline().split()))) ans=inf for bit in range(1<<M-m): c=0 for i in range(M-m): if bit&1<<i: c^=1<<A[m+i] c^=1<<B[m+i] ans=min(ans,dct[C^c]+sum(1 for i in range(M-m) if bit&1<<i)) if ans==inf: ans=-1 print(ans)