Submission #1032971

#TimeUsernameProblemLanguageResultExecution timeMemory
1032971vjudge1Beads and wires (APIO14_beads)C++17
0 / 100
3 ms5208 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define double long double #define all(x) x.begin(), x.end() #define f first #define s second #define pi pair<int, int> string abc = "abcdefghijklmnopqrstuvwxyz"; const int N = 2e5+7; vector<pair<int, int>> adj[N]; int dp[2][N]; void dfs(int u, int p, int sz){ // cout << "st " << u << " " << p << " " << sz << endl; if(u != 1 && adj[u].size() == 1){ dp[1][u] = dp[0][u] = 0; return; } dp[1][u] = dp[0][u]=0; vector<pair<int, int>> v; // cout << "st dfs" << endl; // cout << adj[u].size() << endl; for(auto x : adj[u]){ if(x.f != p){ // cout << "ad " << u << " " << x.f << endl; dfs(x.f, u, x.s); dp[0][u]+=max(dp[1][x.f], dp[0][x.f]); v.push_back({x.s-dp[1][x.f]+dp[0][x.f], max(dp[1][x.f], dp[0][x.f])}); // cout << "ed " << u << " " << x.f << endl; } } // cout << "en dfs" << endl; if(v.size() == 0){ dp[1][u]=dp[0][u]; return; } sort(v.rbegin(), v.rend()); int mx = 0; if(v.size() > 1) mx = v[0].f+v[1].f; if(v.size() > 0) dp[1][u]=max(dp[0][u], dp[0][u]+v[0].f+sz); else dp[1][u]=dp[0][u]; //checkear esto if(mx > 0){ dp[0][u]+=mx; } // cout << "en " << u << endl; return; } void solve(){ int n; cin >> n; for(int i = 1; i < n; i++){ int a, b, c; cin >> a >> b >> c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } if(n == 1 || n == 2){ cout << 0 << endl; return; } dfs(1, -1, 0); cout << dp[0][1] << endl; // for(int i = 0; i <= n; i++){ // cout << i << " " << dp[0][i] << " " << dp[1][i] << endl; // } } signed main() { // ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...