結果
問題 | No.2236 Lights Out On Simple Graph |
ユーザー | 👑 seekworser |
提出日時 | 2023-03-01 22:23:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,916 ms / 4,000 ms |
コード長 | 1,390 bytes |
コンパイル時間 | 447 ms |
コンパイル使用メモリ | 87,296 KB |
実行使用メモリ | 285,844 KB |
最終ジャッジ日時 | 2023-10-15 02:46:02 |
合計ジャッジ時間 | 86,652 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
71,416 KB |
testcase_01 | AC | 80 ms
71,324 KB |
testcase_02 | AC | 80 ms
71,472 KB |
testcase_03 | AC | 2,842 ms
285,844 KB |
testcase_04 | AC | 1,192 ms
266,912 KB |
testcase_05 | AC | 80 ms
71,604 KB |
testcase_06 | AC | 1,888 ms
285,776 KB |
testcase_07 | AC | 2,068 ms
172,228 KB |
testcase_08 | AC | 78 ms
71,332 KB |
testcase_09 | AC | 77 ms
71,432 KB |
testcase_10 | AC | 619 ms
160,948 KB |
testcase_11 | AC | 339 ms
77,840 KB |
testcase_12 | AC | 698 ms
161,024 KB |
testcase_13 | AC | 148 ms
83,816 KB |
testcase_14 | AC | 1,340 ms
266,940 KB |
testcase_15 | AC | 126 ms
80,836 KB |
testcase_16 | AC | 157 ms
84,692 KB |
testcase_17 | AC | 408 ms
114,224 KB |
testcase_18 | AC | 100 ms
76,828 KB |
testcase_19 | AC | 248 ms
93,268 KB |
testcase_20 | AC | 1,303 ms
267,040 KB |
testcase_21 | AC | 246 ms
93,116 KB |
testcase_22 | AC | 2,632 ms
285,716 KB |
testcase_23 | AC | 2,559 ms
285,760 KB |
testcase_24 | AC | 1,364 ms
266,928 KB |
testcase_25 | AC | 390 ms
114,280 KB |
testcase_26 | AC | 2,530 ms
285,488 KB |
testcase_27 | AC | 1,248 ms
267,036 KB |
testcase_28 | AC | 1,410 ms
266,936 KB |
testcase_29 | AC | 237 ms
93,384 KB |
testcase_30 | AC | 2,625 ms
285,784 KB |
testcase_31 | AC | 2,614 ms
285,648 KB |
testcase_32 | AC | 2,723 ms
285,748 KB |
testcase_33 | AC | 2,581 ms
285,780 KB |
testcase_34 | AC | 2,593 ms
285,736 KB |
testcase_35 | AC | 2,499 ms
285,684 KB |
testcase_36 | AC | 2,916 ms
285,836 KB |
testcase_37 | AC | 2,568 ms
285,716 KB |
testcase_38 | AC | 2,881 ms
168,716 KB |
testcase_39 | AC | 2,561 ms
81,848 KB |
testcase_40 | AC | 1,049 ms
169,548 KB |
testcase_41 | AC | 234 ms
93,024 KB |
testcase_42 | AC | 623 ms
121,476 KB |
testcase_43 | AC | 159 ms
81,528 KB |
testcase_44 | AC | 2,465 ms
273,792 KB |
testcase_45 | AC | 2,360 ms
268,484 KB |
testcase_46 | AC | 2,394 ms
271,860 KB |
testcase_47 | AC | 2,109 ms
272,208 KB |
testcase_48 | AC | 2,691 ms
285,708 KB |
testcase_49 | AC | 2,177 ms
171,612 KB |
testcase_50 | AC | 140 ms
77,748 KB |
testcase_51 | AC | 510 ms
97,432 KB |
testcase_52 | AC | 132 ms
78,848 KB |
testcase_53 | AC | 82 ms
71,600 KB |
testcase_54 | AC | 1,233 ms
164,652 KB |
testcase_55 | AC | 2,236 ms
120,740 KB |
testcase_56 | AC | 1,816 ms
100,952 KB |
testcase_57 | AC | 1,956 ms
121,752 KB |
testcase_58 | AC | 1,978 ms
100,972 KB |
testcase_59 | AC | 1,980 ms
97,860 KB |
ソースコード
MSK1 = 0x55555555555555555555555555555555 MSK2 = 0x33333333333333333333333333333333 MSK3 = 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f MSK4 = 0x00ff00ff00ff00ff00ff00ff00ff00ff MSK5 = 0x0000ffff0000ffff0000ffff0000ffff MSK6 = 0x00000000ffffffff00000000ffffffff MSK7 = 0x0000000000000000ffffffffffffffff def popcnt(x): x=(x & MSK1) + ((x>>1) & MSK1) x=(x & MSK2) + ((x>>2) & MSK2) x=(x & MSK3) + ((x>>4) & MSK3) x=(x & MSK4) + ((x>>8) & MSK4) x=(x & MSK5) + ((x>>16) & MSK5) x=(x & MSK6) + ((x>>32) & MSK6) x=(x & MSK7) + ((x>>64) & MSK7) return x n,m = map(int,input().split()) a = [] b = [] for _ in range(m): ai, bi = map(int,input().split()) a.append(ai-1) b.append(bi-1) cv = list(map(int,input().split())) c = 0 for i in range(n): if cv[i]: c += (1 << i) seen = set() val = dict() m1 = m // 2 m2 = m - m1 for bt in range((1 << m1)): l = 0 for i in range(m1): if (bt >> i) & 1: l ^= (1 << a[i]) l ^= (1 << b[i]) if l in seen: val[l] = min(val[l], popcnt(bt)) else: val[l] = popcnt(bt) seen.add(l) ans = 100000000 for bt in range(1 << m2): l = c for i in range(m2): if (bt >> i) & 1: l ^= (1 << a[m1+i]) l ^= (1 << b[m1+i]) if l in seen: ans = min(ans, val[l] + popcnt(bt)) if ans == 100000000: print(-1) else: print(ans)