Submission #713088

#	Time	Username	Problem	Language	Result	Execution time	Memory
713088		bin9638	Beads and wires (APIO14_beads)	C++17	28 / 100	1070 ms	8404 KiB

beads

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define N 200010
#define ii pair<int,int>
#define fs first
#define sc second
#define ld double
#define int ll

int dp[N][2],n,root;
vector<ii>g[N];

void selfmax(int&u,int v)
{
    u=max(u,v);
}

void DFS(int u,int p)
{
    dp[u][0]=0;
    for(auto v:g[u])
        if(v.sc!=p)
            DFS(v.sc,u);
    //dp[u][0]
    int f[3];
    f[0]=f[1]=f[2]=-1e12;
    for(auto v:g[u])
        if(v.sc!=p)
        {
            dp[u][0]+=max(dp[v.sc][0],dp[v.sc][1]+v.fs);
             if(u==root)
             {
                f[2]=dp[v.sc][0]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs);
                sort(f,f+3,greater<int>());
             }
        }
    int dm=dp[u][0];
    if(u==root)
        selfmax(dp[u][0],dp[u][0]+f[0]+f[1]);
    //dp[v.sc][1]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs)
    //dp[u][1]
    for(auto v:g[u])
        if(v.sc!=p)
        {
            int sum=dm-max(dp[v.sc][0],dp[v.sc][1]+v.fs);
            selfmax(dp[u][1],dp[v.sc][0]+v.fs+sum);
        }
    //cout<<u<<" "<<dp[u][0]<<" "<<dp[u][1]<<endl;
}

int32_t main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    int sum=0;
    for(int i=1;i<n;i++)
    {
        int u,v,L;
        cin>>u>>v>>L;
        g[u].pb({L,v});
        g[v].pb({L,u});
        sum+=L;
    }
    int res=0;
    //cout<<sum<<endl;
    for(int i=1;i<=n;i++)
    {
         memset(dp,-0x3f3f,sizeof(dp));
        root=i;
        DFS(i,0);
        res=max(res,dp[i][0]);
    }
    cout<<res;
    return 0;
}

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