Submission #197728

#	Time	Username	Problem	Language	Result	Execution time	Memory
197728		moonrabbit2	Beads and wires (APIO14_beads)	C++17	100 / 100	250 ms	26328 KiB

beads

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef vector<vector<ll>> mat;
const ll mod=1e9+7;
const int N=2e5+5;
int n,ans,dp1[N],dp2[N],dp3[N],dp4[N],val[N];
vector<pii> g[N];
//dp1 : 없/끝, dp2 : 없/부모로, dp3 : 있/끝, dp4 : 있/부모로
void dfs(int x,int p){
    vector<int> v;
    dp2[x]=dp3[x]=dp4[x]=-1e9;
    int s=0;
    for(auto &it : g[x]) if(it.fi!=p){
        int u=it.fi,c=it.se;
        dfs(u,x);
        val[u]=max(dp1[u],dp2[u]+c);
        dp1[x]+=max(dp1[u],dp2[u]+c);
        v.emplace_back(dp1[u]-val[u]+c);
        s+=val[u];
    }
    sort(v.begin(),v.end()); reverse(v.begin(),v.end());
    for(auto &it : g[x]) if(it.fi!=p){
        int u=it.fi,c=it.se;
        dp2[x]=max(dp2[x],dp1[x]-val[u]+dp1[u]+c);
        dp3[x]=max(dp3[x],dp1[x]-val[u]+max(dp3[u],dp4[u]+c));
        dp4[x]=max(dp4[x],dp1[x]-val[u]+dp3[u]+c);
    }
    if(v.size()>=2){
        for(auto &it : g[x]) if(it.fi!=p){
            int u=it.fi,c=it.se;
            if(dp1[u]-val[u]+c==v[0]) dp3[x]=max(dp3[x],dp1[x]-val[u]+max(dp1[u],dp3[u])+c+v[1]);
            else dp3[x]=max(dp3[x],dp1[x]-val[u]+max(dp1[u],dp3[u])+c+v[0]);
        }
    }
    //cout<<x<<" : "<<dp1[x]<<" "<<dp2[x]<<" "<<dp3[x]<<" "<<dp4[x]<<"\n";
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
	cin>>n; int s=0;
    for(int u,v,c,i=1;i<n;i++){
        cin>>u>>v>>c;
        s+=c;
        g[u].emplace_back(v,c);
        g[v].emplace_back(u,c);
    }
    dfs(1,0);
    cout<<max(dp1[1],dp3[1]);
    return 0;
}

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