Submission #351266

#	Time	Username	Problem	Language	Result	Execution time	Memory
351266		denkendoemeer	Beads and wires (APIO14_beads)	C++14	100 / 100	228 ms	23172 KiB

beads

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
vector<pair<int,int>>g[200005];
int dp[200005][4];
void dfs(int nod,int t)
{
    dp[nod][0]=dp[nod][1]=0;
    dp[nod][2]=dp[nod][3]=-inf;
    for(auto it:g[nod]){
        if (it.first!=t){
            dfs(it.first,nod);
            int a,b,c,d;
            a=max(dp[nod][0]+max(dp[it.first][1],dp[it.first][2]+it.second),dp[nod][1]+dp[it.first][3]+it.second);
            a=max(a,max(dp[nod][2]+max(dp[it.first][0],dp[it.first][1]),dp[nod][3]+dp[it.first][1])+it.second);
            a=max(a,dp[nod][1]+max(dp[it.first][0],dp[it.first][1]));
            b=dp[nod][1]+max(dp[it.first][1],dp[it.first][2]+it.second);
            c=max(dp[nod][2]+max(dp[it.first][2]+it.second,dp[it.first][1]),dp[nod][1]+dp[it.first][1]+it.second);
            d=max(dp[nod][3]+max(dp[it.first][2]+it.second,dp[it.first][1]),dp[nod][1]+max(dp[it.first][0],dp[it.first][1])+it.second);
            dp[nod][0]=a;
            dp[nod][1]=b;
            dp[nod][2]=c;
            dp[nod][3]=d;
        }
    }
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,i,a,b,c;
    scanf("%d",&n);
    for(i=1;i<n;i++){
        scanf("%d%d%d",&a,&b,&c);
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    dfs(1,0);
    printf("%d\n",max(dp[1][0],dp[1][1]));
return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
beads.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |         scanf("%d%d%d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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