Submission #100234

#	Time	Username	Problem	Language	Result	Execution time	Memory
100234		TadijaSebez	Beads and wires (APIO14_beads)	C++11	0 / 100	6 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;
	dp[u][0]=dp[u][1]=-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);
	}
	for(auto e:E[u]) if(e.first!=p)
	{
		dp[u][1]=max(dp[u][1],sum-dp[e.first][1]+dp[e.first][0]+e.second+w);
	}
	dp[u][0]=sum;
	for(int i=0;i<E[u].size();i++) if(E[u][i].first!=p)
		for(int j=i+1;j<E[u].size();j++) if(E[u][j].first!=p)
		{
			int v1=E[u][i].first;
			int w1=E[u][i].second;
			int v2=E[u][j].first;
			int w2=E[u][j].second;
			dp[u][0]=max(dp[u][0],sum-dp[v1][1]-dp[v2][1]+dp[v1][0]+dp[v2][0]+w1+w2);
		}
	dp[u][1]=max(dp[u][1],dp[u][0]);
	//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));
	Solve(1,0,0);
	printf("%lld\n",dp[1][0]);
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void Solve(int, int, int)':
beads.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++) if(E[u][i].first!=p)
              ~^~~~~~~~~~~~
beads.cpp:28:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=i+1;j<E[u].size();j++) if(E[u][j].first!=p)
                 ~^~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
beads.cpp:44: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