Submission #116611

#	Time	Username	Problem	Language	Result	Execution time	Memory
116611		jangwonyoung	Beads and wires (APIO14_beads)	C++14	100 / 100	250 ms	20412 KiB

beads

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int N=2e5+1;
int n;
int dp[N][4];
int p[N],pl[N];
int z[4];
vector<pair<int,int> >adj[N];
void dfs(int id){
    for(auto cur:adj[id]){
        if(cur.se==p[id]) continue;
        p[cur.se]=id,pl[cur.se]=cur.fi;
        dfs(cur.se);
    }
}
void solve(int id){
    for(auto cur:adj[id]){//doesnt take node i as merger
        if(cur.se==p[id]) continue;
        solve(cur.se);
    }
    z[0]=z[1]=z[2]=z[3]=-2e9;
    z[1]=0;
    for(auto cur:adj[id]){//doesnt take node i as merger
        if(cur.se==p[id]) continue;
        z[3]=max(z[3]+max(dp[cur.se][0],dp[cur.se][1]),z[1]+max(dp[cur.se][2],dp[cur.se][3]));
        z[1]=z[1]+max(dp[cur.se][0],dp[cur.se][1]);
    }
    dp[id][1]=max(dp[id][1],z[1]);dp[id][3]=max(dp[id][3],max(z[1],z[3]));
    z[0]=z[1]=z[2]=z[3]=-2e9;z[0]=0;
    for(auto cur:adj[id]){//merge horizontally
        if(cur.se==p[id]) continue;
        z[3]=z[3]+max(dp[cur.se][0],dp[cur.se][1]);
        z[3]=max(z[3],max(z[2]+dp[cur.se][1],z[1]+dp[cur.se][3])+pl[cur.se]);
        z[2]=max(z[2]+max(dp[cur.se][0],dp[cur.se][1]),z[0]+dp[cur.se][3]+pl[cur.se]);
        z[1]=max(z[1]+max(dp[cur.se][0],dp[cur.se][1]),z[0]+dp[cur.se][1]+pl[cur.se]);
        z[0]=z[0]+max(dp[cur.se][0],dp[cur.se][1]);
    }
    dp[id][3]=max(dp[id][3],z[3]);
    if(id==1) return;
    z[0]=z[1]=z[2]=z[3]=-2e9;z[0]=0;
    for(auto cur:adj[id]){//merge vertically
        if(cur.se==p[id]) continue;
        z[2]=max(z[2]+max(dp[cur.se][0],dp[cur.se][1]),z[0]+dp[cur.se][3]+pl[cur.se]);
        z[1]=max(z[1]+max(dp[cur.se][0],dp[cur.se][1]),z[0]+dp[cur.se][1]+pl[cur.se]);
        z[0]=z[0]+max(dp[cur.se][0],dp[cur.se][1]);
    }
    dp[id][2]=max(dp[id][2],z[2]+pl[id]);dp[id][0]=max(dp[id][0],z[1]+pl[id]);
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i=1; i<n ;i++){
        int u,v,w;cin >> u >> v >> w;
        adj[u].pb({w,v});adj[v].pb({w,u});
    }
    dfs(1);
    solve(1);
    cout << max(max(dp[1][0],dp[1][1]),max(dp[1][2],dp[1][3])) << '\n';
}

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