結果
問題 | No.2677 Minmax Independent Set |
ユーザー | NokonoKotlin |
提出日時 | 2024-03-13 21:00:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 641 ms / 2,000 ms |
コード長 | 886 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 81,572 KB |
実行使用メモリ | 123,004 KB |
最終ジャッジ日時 | 2024-03-15 20:54:28 |
合計ジャッジ時間 | 19,966 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
55,604 KB |
testcase_01 | AC | 40 ms
55,604 KB |
testcase_02 | AC | 40 ms
55,604 KB |
testcase_03 | AC | 39 ms
55,604 KB |
testcase_04 | AC | 40 ms
55,604 KB |
testcase_05 | AC | 513 ms
117,468 KB |
testcase_06 | AC | 519 ms
117,464 KB |
testcase_07 | AC | 514 ms
117,464 KB |
testcase_08 | AC | 508 ms
117,464 KB |
testcase_09 | AC | 514 ms
117,468 KB |
testcase_10 | AC | 441 ms
120,936 KB |
testcase_11 | AC | 439 ms
120,932 KB |
testcase_12 | AC | 437 ms
117,200 KB |
testcase_13 | AC | 540 ms
119,088 KB |
testcase_14 | AC | 507 ms
118,092 KB |
testcase_15 | AC | 551 ms
117,656 KB |
testcase_16 | AC | 641 ms
117,972 KB |
testcase_17 | AC | 637 ms
118,108 KB |
testcase_18 | AC | 397 ms
102,056 KB |
testcase_19 | AC | 456 ms
108,124 KB |
testcase_20 | AC | 187 ms
87,796 KB |
testcase_21 | AC | 474 ms
111,324 KB |
testcase_22 | AC | 115 ms
79,564 KB |
testcase_23 | AC | 48 ms
63,076 KB |
testcase_24 | AC | 41 ms
55,604 KB |
testcase_25 | AC | 40 ms
55,604 KB |
testcase_26 | AC | 41 ms
55,604 KB |
testcase_27 | AC | 47 ms
61,004 KB |
testcase_28 | AC | 346 ms
123,004 KB |
testcase_29 | AC | 458 ms
117,340 KB |
testcase_30 | AC | 39 ms
55,604 KB |
testcase_31 | AC | 40 ms
55,604 KB |
testcase_32 | AC | 40 ms
55,604 KB |
testcase_33 | AC | 40 ms
55,604 KB |
testcase_34 | AC | 40 ms
55,604 KB |
testcase_35 | AC | 41 ms
55,604 KB |
testcase_36 | AC | 42 ms
55,604 KB |
testcase_37 | AC | 45 ms
61,004 KB |
testcase_38 | AC | 49 ms
63,072 KB |
testcase_39 | AC | 73 ms
75,064 KB |
testcase_40 | AC | 89 ms
77,236 KB |
testcase_41 | AC | 91 ms
77,604 KB |
testcase_42 | AC | 98 ms
78,028 KB |
testcase_43 | AC | 124 ms
80,912 KB |
testcase_44 | AC | 191 ms
85,956 KB |
testcase_45 | AC | 288 ms
97,096 KB |
testcase_46 | AC | 573 ms
116,664 KB |
testcase_47 | AC | 575 ms
116,944 KB |
testcase_48 | AC | 606 ms
117,072 KB |
testcase_49 | AC | 571 ms
117,200 KB |
testcase_50 | AC | 160 ms
93,028 KB |
testcase_51 | AC | 75 ms
77,452 KB |
testcase_52 | AC | 293 ms
114,608 KB |
testcase_53 | AC | 284 ms
109,968 KB |
testcase_54 | AC | 78 ms
77,224 KB |
testcase_55 | AC | 377 ms
121,424 KB |
testcase_56 | AC | 377 ms
120,900 KB |
testcase_57 | AC | 379 ms
121,032 KB |
testcase_58 | AC | 389 ms
121,416 KB |
testcase_59 | AC | 413 ms
120,944 KB |
testcase_60 | AC | 285 ms
117,728 KB |
testcase_61 | AC | 269 ms
117,328 KB |
testcase_62 | AC | 265 ms
116,944 KB |
testcase_63 | AC | 275 ms
120,016 KB |
ソースコード
#!/usr/bin/python3 # 非再帰全方位木DP # https://qiita.com/Kiri8128/items/a011c90d25911bdb3ed3 を改変 import sys input = sys.stdin.readline from collections import deque # input N = int(input()) X = [[] for i in range(N)] for i in range(N-1): x, y = map(int, input().split()) X[x-1].append(y-1) X[y-1].append(x-1) # topological sort P = [-1] * N Q = deque([0]) R = [] while Q: i = deque.popleft(Q) R.append(i) for a in X[i]: if a != P[i]: P[a] = i X[a].remove(i) deque.append(Q, a) # dp dp = [(0, 1)] * N for i in R[::-1]: for j in X[i]: dp[i] = (dp[i][0] + max(dp[j]), dp[i][1] + dp[j][0]) for i in R: for j in X[i]: dp_par = (dp[i][0] - max(dp[j][0], dp[j][1]), dp[i][1] - dp[j][0]) dp[j] = (dp[j][0] + max(dp_par), dp[j][1] + dp_par[0]) print(min([a[1] for a in dp]))