結果
問題 | No.2236 Lights Out On Simple Graph |
ユーザー |
![]() |
提出日時 | 2023-03-04 01:29:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,444 ms / 4,000 ms |
コード長 | 700 bytes |
コンパイル時間 | 260 ms |
コンパイル使用メモリ | 82,276 KB |
実行使用メモリ | 254,784 KB |
最終ジャッジ日時 | 2024-09-18 00:52:19 |
合計ジャッジ時間 | 42,555 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
from collections import defaultdict n,m = map(int,input().split()) a = [0] * m b = [0] * m for i in range(m): a[i], b[i] = map(int,input().split()) a[i] -= 1 b[i] -= 1 c = list(map(int,input().split())) q = 0 for i in range(n): q ^= c[i] << i r = m - m//2 v = defaultdict(lambda: 10 ** 9) for i in range(1 << r): cnt = 0 h = 0 for j in range(r): if (i >> j & 1): cnt += 1 h ^= 1 << a[m // 2 + j] h ^= 1 << b[m // 2 + j] v[h] = min(v[h], cnt) r2 = m//2 ans = 10 ** 9 for i in range(1 << r2): cnt = 0 h = 0 for j in range(r2): if (i >> j & 1): cnt += 1 h ^= 1 << a[j] h ^= 1 << b[j] ans = min(ans, v[q ^ h] + cnt) if ans >= 10 ** 7: print(-1) else: print(ans)