結果
問題 | No.2677 Minmax Independent Set |
ユーザー | 👑 nu50218 |
提出日時 | 2023-12-01 01:13:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 664 ms / 2,000 ms |
コード長 | 886 bytes |
コンパイル時間 | 180 ms |
コンパイル使用メモリ | 81,572 KB |
実行使用メモリ | 123,004 KB |
最終ジャッジ日時 | 2024-03-15 20:51:11 |
合計ジャッジ時間 | 20,273 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
55,604 KB |
testcase_01 | AC | 38 ms
55,604 KB |
testcase_02 | AC | 39 ms
55,604 KB |
testcase_03 | AC | 40 ms
55,604 KB |
testcase_04 | AC | 39 ms
55,604 KB |
testcase_05 | AC | 518 ms
117,468 KB |
testcase_06 | AC | 498 ms
117,464 KB |
testcase_07 | AC | 509 ms
117,464 KB |
testcase_08 | AC | 507 ms
117,464 KB |
testcase_09 | AC | 516 ms
117,468 KB |
testcase_10 | AC | 426 ms
120,944 KB |
testcase_11 | AC | 421 ms
120,928 KB |
testcase_12 | AC | 428 ms
117,328 KB |
testcase_13 | AC | 536 ms
119,092 KB |
testcase_14 | AC | 515 ms
118,092 KB |
testcase_15 | AC | 558 ms
117,664 KB |
testcase_16 | AC | 649 ms
117,972 KB |
testcase_17 | AC | 664 ms
118,108 KB |
testcase_18 | AC | 401 ms
102,056 KB |
testcase_19 | AC | 485 ms
108,124 KB |
testcase_20 | AC | 204 ms
87,796 KB |
testcase_21 | AC | 553 ms
111,324 KB |
testcase_22 | AC | 122 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 | 40 ms
55,604 KB |
testcase_27 | AC | 47 ms
61,004 KB |
testcase_28 | AC | 382 ms
123,004 KB |
testcase_29 | AC | 464 ms
117,340 KB |
testcase_30 | AC | 39 ms
55,604 KB |
testcase_31 | AC | 41 ms
55,604 KB |
testcase_32 | AC | 40 ms
55,604 KB |
testcase_33 | AC | 39 ms
55,604 KB |
testcase_34 | AC | 40 ms
55,604 KB |
testcase_35 | AC | 40 ms
55,604 KB |
testcase_36 | AC | 41 ms
55,604 KB |
testcase_37 | AC | 44 ms
61,004 KB |
testcase_38 | AC | 48 ms
63,072 KB |
testcase_39 | AC | 73 ms
75,064 KB |
testcase_40 | AC | 88 ms
77,236 KB |
testcase_41 | AC | 92 ms
77,604 KB |
testcase_42 | AC | 102 ms
78,028 KB |
testcase_43 | AC | 136 ms
80,912 KB |
testcase_44 | AC | 191 ms
85,956 KB |
testcase_45 | AC | 312 ms
97,096 KB |
testcase_46 | AC | 587 ms
116,664 KB |
testcase_47 | AC | 604 ms
116,944 KB |
testcase_48 | AC | 606 ms
117,072 KB |
testcase_49 | AC | 591 ms
117,200 KB |
testcase_50 | AC | 174 ms
93,008 KB |
testcase_51 | AC | 79 ms
77,456 KB |
testcase_52 | AC | 321 ms
114,608 KB |
testcase_53 | AC | 289 ms
109,968 KB |
testcase_54 | AC | 77 ms
77,224 KB |
testcase_55 | AC | 413 ms
121,412 KB |
testcase_56 | AC | 417 ms
120,900 KB |
testcase_57 | AC | 413 ms
121,032 KB |
testcase_58 | AC | 417 ms
121,416 KB |
testcase_59 | AC | 420 ms
120,956 KB |
testcase_60 | AC | 283 ms
117,728 KB |
testcase_61 | AC | 271 ms
117,328 KB |
testcase_62 | AC | 260 ms
116,944 KB |
testcase_63 | AC | 273 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]))