Submission #125113

#	Time	Username	Problem	Language	Result	Execution time	Memory
125113		TadijaSebez	Beads and wires (APIO14_beads)	C++11	28 / 100	1080 ms	3192 KiB

beads

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int inf=1e9+7;
vector<pair<int,int>> E[N];
int dp[N][2];
void DFS(int u, int p, int w)
{
	dp[u][0]=0;
	int mx=-inf;
	for(auto e:E[u]) if(e.first!=p)
	{
		int v=e.first;
		DFS(v,u,e.second);
		dp[u][0]+=max(dp[v][0],dp[v][1]);
		mx=max(mx,dp[v][0]+w+e.second-max(dp[v][0],dp[v][1]));
	}
	dp[u][1]=dp[u][0]+mx;
}
int main()
{
	int n,u,v,w;
	scanf("%i",&n);
	for(int i=1;i<n;i++) scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w});
    int ans=-inf;
    for(int i=1;i<=n;i++) DFS(i,0,0),ans=max(ans,dp[i][0]);
    printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
beads.cpp:25:64: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<n;i++) scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w});
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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