제출 #135210

#제출 시각아이디문제언어결과실행 시간메모리
135210fredbr구슬과 끈 (APIO14_beads)C++17
28 / 100
1064 ms1272 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") using namespace std; int const maxn = 10001; struct Edge { int u, w, id; }; struct FEdge { int a, b, w; }; vector<Edge> v[maxn]; vector<FEdge> eg; int dp[2*maxn][2]; inline int invalid(int x, int p) { return v[x].size() == 1 and v[x].front().u == p; } int solve(int id, int t = 0) { int x = eg[id].b; int p = eg[id].a; if (dp[x][t] >= 0) return dp[x][t]; int d = 0; if (t == 0) { for (Edge const& e : v[x]) { if (e.u == p) continue; if (!invalid(e.u, x)) { d += max(solve(e.id, 1) + e.w, solve(e.id, 0)); } } } else { int sum = solve(id, 0); for (Edge const& e : v[x]) { if (e.u == p) continue; if (!invalid(e.u, x)) d = max(d, sum - max(solve(e.id, 1) + e.w, solve(e.id, 0)) + e.w + solve(e.id, 0)); else d = max(d, sum + e.w); } } return dp[x][t] = d; } inline int test(int x) { memset(dp, -1, sizeof(dp)); return max(solve(x), solve(x, 1) + eg[x].w); } int main() { ios::sync_with_stdio(false), cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n-1; i++) { int a, b, w; cin >> a >> b >> w; v[a].push_back({b, w, i*2}); v[b].push_back({a, w, i*2+1}); eg.push_back({a, b, w}); eg.push_back({b, a, w}); } int ans = 0; for (int i = 0; i < 2*n - 2; i++) ans = max(ans, test(i)); cout << ans << "\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...