結果
| 問題 | No.2677 Minmax Independent Set |
| ユーザー |
👑  nu50218
|
| 提出日時 | 2023-12-01 01:37:28 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 1,323 bytes |
| コンパイル時間 | 208 ms |
| コンパイル使用メモリ | 81,700 KB |
| 実行使用メモリ | 575,564 KB |
| 最終ジャッジ日時 | 2024-03-15 20:51:30 |
| 合計ジャッジ時間 | 19,406 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 36 ms
53,460 KB |
| testcase_01 | AC | 36 ms
53,460 KB |
| testcase_02 | AC | 36 ms
53,460 KB |
| testcase_03 | AC | 36 ms
53,460 KB |
| testcase_04 | AC | 36 ms
53,460 KB |
| testcase_05 | AC | 1,783 ms
253,192 KB |
| testcase_06 | AC | 1,873 ms
254,104 KB |
| testcase_07 | AC | 1,656 ms
247,304 KB |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| testcase_10 | AC | 1,050 ms
168,556 KB |
| testcase_11 | AC | 1,046 ms
168,448 KB |
| testcase_12 | TLE | - |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | MLE | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
ソースコード
#!/usr/bin/python3 import sys sys.setrecursionlimit(10**6) def main(): N = int(input()) to = [[] for i in range(N)] for i in range(N-1): x, y = map(int, input().split()) x -= 1 y -= 1 to[x].append(y) to[y].append(x) # https://snuke.hatenablog.com/entry/2019/01/16/203626 を改変 pi = [0] * N deg = [0] * N dp = [[] for i in range(N)] ans = [0] * N def dfs(v, p=-1): deg[v] = len(to[v]) res = (0, 0) dp[v] = [0]*deg[v] for i in range(deg[v]): u = to[v][i] if u == p: pi[v] = i continue dp[v][i] = dfs(u, v) val = (max(dp[v][i]), dp[v][i][0]) res = (res[0] + val[0], res[1] + val[1]) return (res[0], res[1] + 1) def bfs(v, res_p=0, p=-1): if p != -1: dp[v][pi[v]] = res_p dpl = [(0, 0)]*(deg[v]+1) for i in range(deg[v]): dpl[i+1] = (dpl[i][0] + max(dp[v][i]), dpl[i][1] + dp[v][i][0]) dpr = [(0, 0)]*(deg[v]+1) for i in range(deg[v]-1,-1,-1): dpr[i] = (dpr[i+1][0] + max(dp[v][i]), dpr[i+1][1] + dp[v][i][0]) ans[v] = (dpr[0][0], dpr[0][1] + 1) for i in range(deg[v]): u = to[v][i] if u == p: continue val = (dpl[i][0] + dpr[i+1][0], dpl[i][1] + dpr[i+1][1] + 1) bfs(u, val, v) dfs(0) bfs(0) # 答え出力 print(min([x[1] for x in ans])) main()