結果
問題 | No.1488 Max Score of the Tree |
ユーザー | sten_san |
提出日時 | 2021-04-23 22:44:13 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 212 ms / 2,000 ms |
コード長 | 3,150 bytes |
コンパイル時間 | 2,628 ms |
コンパイル使用メモリ | 224,060 KB |
実行使用メモリ | 239,540 KB |
最終ジャッジ日時 | 2023-09-17 12:46:24 |
合計ジャッジ時間 | 6,883 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 198 ms
229,308 KB |
testcase_01 | AC | 191 ms
219,916 KB |
testcase_02 | AC | 201 ms
231,708 KB |
testcase_03 | AC | 207 ms
239,408 KB |
testcase_04 | AC | 209 ms
239,492 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 53 ms
61,424 KB |
testcase_07 | AC | 123 ms
138,284 KB |
testcase_08 | AC | 86 ms
97,384 KB |
testcase_09 | AC | 64 ms
69,292 KB |
testcase_10 | AC | 126 ms
142,608 KB |
testcase_11 | AC | 212 ms
239,436 KB |
testcase_12 | AC | 3 ms
4,584 KB |
testcase_13 | AC | 32 ms
37,028 KB |
testcase_14 | AC | 101 ms
115,704 KB |
testcase_15 | AC | 66 ms
72,888 KB |
testcase_16 | AC | 13 ms
15,988 KB |
testcase_17 | AC | 41 ms
46,316 KB |
testcase_18 | AC | 138 ms
160,388 KB |
testcase_19 | AC | 81 ms
90,328 KB |
testcase_20 | AC | 34 ms
37,880 KB |
testcase_21 | AC | 17 ms
20,692 KB |
testcase_22 | AC | 63 ms
71,220 KB |
testcase_23 | AC | 2 ms
4,504 KB |
testcase_24 | AC | 2 ms
4,376 KB |
testcase_25 | AC | 2 ms
4,376 KB |
testcase_26 | AC | 49 ms
56,304 KB |
testcase_27 | AC | 9 ms
11,228 KB |
testcase_28 | AC | 24 ms
28,028 KB |
testcase_29 | AC | 32 ms
36,268 KB |
testcase_30 | AC | 165 ms
192,952 KB |
testcase_31 | AC | 209 ms
239,540 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; struct iofast_t { iofast_t() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } } iofast; struct uns_t {} uns; template <typename Element, typename Head, typename ...Args> auto vec(Element init, Head arg, Args ...args) { if constexpr (sizeof...(Args) == 0) return std::vector(arg, init); else return std::vector(arg, vec(init, args...)); } template <typename Element, typename Head, typename ...Args> auto vec(uns_t, Head arg, Args ...args) { return vec(Element(), arg, args...); } template <typename T, typename Compare = less<T>> T &chmin(T &l, T r, Compare &&f = less<T>()) { return l = min(l, r, f); } template <typename T, typename Compare = less<T>> T &chmax(T &l, T r, Compare &&f = less<T>()) { return l = max(l, r, f); } int main() { #define int int64_t int n, k; cin >> n >> k; auto g = vec<tuple<int, int>>(uns, n, 0); auto e = vec<tuple<int, int, int>>(uns, n - 1); for (int i = 0; i < n - 1; ++i) { int a, b, c; cin >> a >> b >> c; --a; --b; g[a].emplace_back(b, c); g[b].emplace_back(a, c); e[i] = { a, b, c }; } auto c = vec<int>(uns, n); auto d = vec<bool>(false, n, n); auto dfs = [&](int v, int p, auto &&dfs) -> int { auto &ans = c[v]; ans = 0; for (auto [next, _] : g[v]) { if (next == p) continue; ans += dfs(next, v, dfs); d[v][next] = true; } ans += ans == 0; return ans; }; dfs(0, -1, dfs); for (auto &[a, b, c] : e) { if (!d[a][b]) { swap(a, b); } } auto value = vec<int>(uns, n - 1); auto weight = vec<int>(uns, n - 1); for (int i = 0; i < n - 1; ++i) { auto [a, b, cost] = e[i]; value[i] = cost * c[b]; weight[i] = cost; } auto dp = vec<int64_t>(0, n, k + 1); auto prev = vec<tuple<int, int>>(uns, n, k + 1); for (int i = 1; i <= n - 1; ++i) { for (int j = 0; j <= k; ++j) { if (weight[i - 1] <= j) { if (auto v = dp[i - 1][j - weight[i - 1]] + value[i - 1]; dp[i][j] < v) { dp[i][j] = v; prev[i][j] = { i - 1, j - weight[i - 1] }; } } if (dp[i][j] < dp[i - 1][j]) { dp[i][j] = dp[i - 1][j]; prev[i][j] = { i - 1, j }; } } } auto choosed = vec<tuple<int, int>>(uns, 0); auto back = [&](int i, int j, auto &&back) -> void { if (i == 0 && j == 0) return; auto [pi, pj] = prev[i][j]; back(pi, pj, back); if (j != pj && weight[i - 1] <= j) { auto [a, b, c] = e[i - 1]; choosed.emplace_back(a, b); } }; back(n - 1, k, back); for (auto [a, b] : choosed) { for (auto &[c, d, cost] : e) { if (a == c && b == d) { cost *= 2; } } } int64_t ans = 0; for (auto [a, b, cost] : e) { ans += c[b] * cost; } cout << ans << endl; }