Submission #338105

#	Time	Username	Problem	Language	Result	Execution time	Memory
338105		ogibogi2004	Beads and wires (APIO14_beads)	C++14	28 / 100	1096 ms	5484 KiB

beads

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
const ll INF=2e15;
ll dp[MAXN][2];
ll par[MAXN];
vector<pair<ll,ll> >g[MAXN];
void dfs(ll u,ll p)
{
	par[u]=p;
	vector<pair<pair<ll,ll>,ll> >ch;
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		dfs(v.first,u);
		ch.push_back({{dp[v.first][0],dp[v.first][1]},v.second});
	}
	dp[u][1]=-INF;
	for(ll i=0;i<ch.size();i++)
	{
		dp[u][0]+=max(ch[i].first.first,ch[i].first.second+ch[i].second);
	}
	for(ll i=0;i<ch.size();i++)
	{
		dp[u][1]=max(dp[u][1],dp[u][0]-max(ch[i].first.first,ch[i].first.second+ch[i].second)+ch[i].first.first+ch[i].second);
	}
}
int main()
{
	ll n;
	cin>>n;
	for(ll i=1;i<n;i++)
	{
		ll x,y,z;
		cin>>x>>y>>z;
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
	ll ans=0;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=n;j++)
		{
			dp[j][0]=0;
			dp[j][1]=-INF;
		}
		dfs(i,0);
		//cout<<i<<" "<<dp[i][0]<<endl;
		ans=max(ans,dp[i][0]);
	}
	cout<<ans<<endl;
return 0;
}
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34

*/

Compilation message (stderr)

beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:20:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(ll i=0;i<ch.size();i++)
      |             ~^~~~~~~~~~
beads.cpp:24:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(ll i=0;i<ch.size();i++)
      |             ~^~~~~~~~~~

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