Submission #100235

#	Time	Username	Problem	Language	Result	Execution time	Memory
100235		TadijaSebez	Beads and wires (APIO14_beads)	C++11	0 / 100	5 ms	4992 KiB

beads

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
const int N=200050;
const ll inf=1e18;
ll dp[N][2];
vector<pair<int,int>> E[N];
void Solve(int u, int p, int w)
{
	ll sum=0,fir=-inf,sec=-inf;
	for(auto e:E[u]) if(e.first!=p)
	{
		Solve(e.first,u,e.second);
		sum+=dp[e.first][1];
		ll dif=dp[e.first][0]-dp[e.first][1]+e.second;
		if(fir<=dif) sec=fir,fir=dif;
		else sec=max(sec,dif);
	}
	dp[u][0]=max(sum,sum+fir+sec);
	dp[u][1]=max(dp[u][0],sum+fir+w);
}
int main()
{
	int n,i,u,v,w;
	scanf("%i",&n);
	for(i=1;i<n;i++) scanf("%i %i %i",&u,&v,&w),E[u].pb(mp(v,w)),E[v].pb(mp(u,w));
	ll ans=0;
	for(int i=1;i<=n;i++) Solve(i,0,0),ans=max(ans,dp[i][0]);
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

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

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