Submission #1138355

#TimeUsernameProblemLanguageResultExecution timeMemory
1138355PekibanBeads and wires (APIO14_beads)C++20
100 / 100
161 ms34384 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back const int N = 2e5 + 5; const ll inf = 1e12; ll dp[N][2][2]; vector<array<int, 2>> g[N]; void dfs(int s, int e = -1) { dp[s][0][0] = dp[s][1][0] = dp[s][1][1] = 0, dp[s][0][1] = -inf; for (auto [u, w] : g[s]) { if (u == e) continue; dfs(u, s); dp[s][0][0] += max(dp[u][0][0], dp[u][1][0] + w); } ll bs = -inf, bs2 = -inf; for (auto [u, w] : g[s]) { if (u == e) continue; bs = max(bs, dp[u][0][0] + w - max(dp[u][0][0], dp[u][1][0] + w)); dp[s][1][0] += max(dp[u][0][0], dp[u][1][0] + w); } dp[s][1][0] += bs; bs = bs2 = -inf; vector<array<ll, 2>> V1 = {{-inf, 0}, {-inf, 0}}, V2 = {{-inf, 0}, {-inf, 0}}; ll S = 0; for (auto [u, w] : g[s]) { if (u == e) continue; V1.pb({dp[u][0][0] + w - max(dp[u][0][0], dp[u][1][0] + w), u}); V2.pb({dp[u][0][1] + w - max(dp[u][0][0], dp[u][1][0] + w), u}); S += max(dp[u][0][0], dp[u][1][0] + w); bs = max(bs, max(dp[u][1][1] + w, dp[u][0][1]) - max(dp[u][0][0], dp[u][1][0] + w)); } sort(V1.begin(), V1.end()); sort(V2.begin(), V2.end()); int sz = V1.size(); // if (s == 1) { // for (auto [a, b] : V1) cout << a << ' ' << b << "||"; // cout << '\n'; // for (auto [a, b] : V2) cout << a << ' ' << b << "||"; // cout << '\n'; // cout << S << ' ' << bs << '\n'; // } dp[s][0][1] = S + max({bs, V1[sz-1][0] + V1[sz-2][0], (V1[sz-1][1] == V2[sz-1][1] ? max(V1[sz-1][0] + V2[sz-2][0], V1[sz-2][0] + V2[sz-1][0]) : V1[sz-1][0] + V2[sz-1][0])}); bs = -inf; for (auto [u, w] : g[s]) { if (u == e) continue; bs = max(bs, dp[u][0][1] + w - max(dp[u][0][0], dp[u][1][0] + w)); dp[s][1][1] += max(dp[u][0][0], dp[u][1][0] + w); } dp[s][1][1] += bs; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i = 1; i < n; ++i) { int u, v, w; cin >> u >> v >> w; g[u].pb({v, w}); g[v].pb({u, w}); } dfs(1); cout << max(dp[1][0][0], dp[1][0][1]) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...