Submission #125122

#	Time	Username	Problem	Language	Result	Execution time	Memory
125122		TadijaSebez	Beads and wires (APIO14_beads)	C++11	100 / 100	245 ms	22372 KiB

beads

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
const int inf=1e9+7;
vector<pair<int,int>> E[N];
int dp[N][2],up[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 ans;
void Solve(int u, int p, int w)
{
	ans=max(ans,max(up[u][0],up[u][1])+dp[u][0]);
	int fir=-inf,sec=-inf,cnt=0;
	for(auto e:E[u]) if(e.first!=p)
	{
		int v=e.first;
		int tmp=dp[v][0]-max(dp[v][0],dp[v][1])+e.second;
		if(fir<tmp) sec=fir,fir=tmp;
		else if(sec<tmp) sec=tmp;
		cnt++;
	}
	for(auto e:E[u]) if(e.first!=p)
	{
		int v=e.first;
		int tmp=dp[v][0]-max(dp[v][0],dp[v][1])+e.second;
		int sum=dp[u][0]-max(dp[v][0],dp[v][1]);
		if(u!=1) up[v][1]=up[u][0]+w+e.second+sum;
		if(cnt>1)
		{
			int add=fir;
			if(fir==tmp) add=sec;
			up[v][1]=max(up[v][1],max(up[u][1],up[u][0])+e.second+add+sum);
		}
		up[v][0]=max(up[u][0],up[u][1])+sum;
		Solve(v,u,e.second);
	}
}
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});
	DFS(1,0,0);
	Solve(1,0,0);
    printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
beads.cpp:54: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: 29 / 29
• Subtask 4: 43 / 43