結果
問題 | No.2236 Lights Out On Simple Graph |
ユーザー | vwxyz |
提出日時 | 2023-12-01 02:33:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,063 ms / 4,000 ms |
コード長 | 745 bytes |
コンパイル時間 | 388 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 273,628 KB |
最終ジャッジ日時 | 2023-12-01 02:35:15 |
合計ジャッジ時間 | 95,201 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
55,604 KB |
testcase_01 | AC | 38 ms
55,604 KB |
testcase_02 | AC | 39 ms
55,604 KB |
testcase_03 | AC | 2,956 ms
272,972 KB |
testcase_04 | AC | 2,135 ms
256,000 KB |
testcase_05 | AC | 39 ms
55,604 KB |
testcase_06 | AC | 2,669 ms
273,620 KB |
testcase_07 | AC | 2,754 ms
256,832 KB |
testcase_08 | AC | 39 ms
55,604 KB |
testcase_09 | AC | 39 ms
55,604 KB |
testcase_10 | AC | 752 ms
143,848 KB |
testcase_11 | AC | 352 ms
76,988 KB |
testcase_12 | AC | 1,130 ms
159,588 KB |
testcase_13 | AC | 195 ms
84,704 KB |
testcase_14 | AC | 1,886 ms
248,852 KB |
testcase_15 | AC | 179 ms
82,536 KB |
testcase_16 | AC | 226 ms
89,080 KB |
testcase_17 | AC | 441 ms
104,380 KB |
testcase_18 | AC | 123 ms
77,504 KB |
testcase_19 | AC | 374 ms
104,612 KB |
testcase_20 | AC | 1,468 ms
248,300 KB |
testcase_21 | AC | 370 ms
106,108 KB |
testcase_22 | AC | 2,970 ms
273,164 KB |
testcase_23 | AC | 2,804 ms
273,620 KB |
testcase_24 | AC | 1,879 ms
248,932 KB |
testcase_25 | AC | 658 ms
141,940 KB |
testcase_26 | AC | 3,063 ms
273,628 KB |
testcase_27 | AC | 1,443 ms
248,016 KB |
testcase_28 | AC | 2,019 ms
256,884 KB |
testcase_29 | AC | 372 ms
105,992 KB |
testcase_30 | AC | 2,978 ms
273,180 KB |
testcase_31 | AC | 2,946 ms
273,172 KB |
testcase_32 | AC | 3,035 ms
273,168 KB |
testcase_33 | AC | 2,747 ms
273,140 KB |
testcase_34 | AC | 2,979 ms
273,124 KB |
testcase_35 | AC | 2,627 ms
265,288 KB |
testcase_36 | AC | 2,417 ms
257,736 KB |
testcase_37 | AC | 2,703 ms
273,616 KB |
testcase_38 | AC | 2,065 ms
119,380 KB |
testcase_39 | AC | 1,945 ms
79,452 KB |
testcase_40 | AC | 1,259 ms
146,704 KB |
testcase_41 | AC | 345 ms
94,580 KB |
testcase_42 | AC | 1,060 ms
181,048 KB |
testcase_43 | AC | 217 ms
80,972 KB |
testcase_44 | AC | 2,404 ms
219,772 KB |
testcase_45 | AC | 3,006 ms
258,220 KB |
testcase_46 | AC | 2,514 ms
252,244 KB |
testcase_47 | AC | 2,719 ms
260,308 KB |
testcase_48 | AC | 2,653 ms
265,416 KB |
testcase_49 | AC | 2,518 ms
256,356 KB |
testcase_50 | AC | 162 ms
77,120 KB |
testcase_51 | AC | 770 ms
127,276 KB |
testcase_52 | AC | 188 ms
78,528 KB |
testcase_53 | AC | 41 ms
55,604 KB |
testcase_54 | AC | 1,754 ms
160,392 KB |
testcase_55 | AC | 2,446 ms
106,212 KB |
testcase_56 | AC | 1,989 ms
97,116 KB |
testcase_57 | AC | 1,994 ms
113,568 KB |
testcase_58 | AC | 2,141 ms
88,916 KB |
testcase_59 | AC | 2,247 ms
89,120 KB |
ソースコード
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)