Submission #1032971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032971		vjudge1	Beads and wires (APIO14_beads)	C++17	0 / 100	3 ms	5208 KiB

beads

#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();
    }
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43