Submission #754143

#	Time	Username	Problem	Language	Result	Execution time	Memory
754143		bgnbvnbv	Beads and wires (APIO14_beads)	C++14	0 / 100	4 ms	5028 KiB

beads

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll dp[maxN][2];
vector<pli>g[maxN];
ll w[maxN];
void dfs(ll u,ll p)
{
    dp[u][0]=0;
    dp[u][1]=-inf;
    vector<pli>vec;
    for(auto zz:g[u])
    {
        if(zz.fi==p) continue;
        w[zz.fi]=zz.se;
        dfs(zz.fi,u);
        dp[u][0]+=max(dp[zz.fi][0],dp[zz.fi][1]);
        vec.pb({-max(dp[zz.fi][0],dp[zz.fi][1])+dp[zz.fi][0]+zz.se,0});
    }
    sort(vec.begin(),vec.end(),greater<pli>());
    ll x=dp[u][0];
    if(vec.size()>=2)
    {
        dp[u][0]=max(dp[u][0],x+vec[0].fi+vec[1].fi);
    }
    if(vec.size()>=1) dp[u][1]=max(dp[u][1],x+vec[0].fi+w[u]);
    vec.clear();
}
ll u,v,c,n;
void solve()
{
    cin >> n;
    for(int i=1;i<n;i++)
    {
        cin >>u >> v >> c;
        g[u].pb({v,c});
        g[v].pb({u,c});
    }
    dfs(1,0);
    cout <<dp[1][0];
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

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