Submission #337393

#	Time	Username	Problem	Language	Result	Execution time	Memory
337393		ogibogi2004	Beads and wires (APIO14_beads)	C++14	0 / 100	2 ms	2688 KiB

beads

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e5+6;
const ll INF=2e15;
ll dp[MAXN][2];
ll dp1[MAXN][3];
vector<pair<ll,ll> >g[MAXN];
ll n;
struct node
{
	ll idx;
	ll pare;
	ll v1,v2,v3;
};
void dfs(int u,int par)
{
	vector<node>children;
	for(auto v:g[u])
	{
		if(v.first==par)continue;
		dfs(v.first,u);
		children.push_back({v.first,v.second,dp[v.first][0],dp[v.first][1]+v.second,dp[v.first][0]+v.second});
	}
	if(children.size()==0)
	{
		dp[u][0]=0;
		dp[u][1]=-INF;
		return;
	}
	dp1[0][0]=max(children[0].v1,children[0].v2);
	dp1[0][1]=children[0].v3;
	dp1[0][2]=-INF;
	for(int i=1;i<children.size();i++)
	{
		dp1[i][0]=-INF;
		dp1[i][1]=-INF;
		dp1[i][2]=-INF;
		dp1[i][0]=max(dp1[i][0],dp1[i-1][0]+children[i].v1);
		dp1[i][0]=max(dp1[i][0],dp1[i-1][0]+children[i].v2);
		dp1[i][1]=max(dp1[i][1],dp1[i-1][1]+children[i].v1);
		dp1[i][1]=max(dp1[i][1],dp1[i-1][1]+children[i].v2);
		dp1[i][2]=max(dp1[i][2],dp1[i-1][2]+children[i].v1);
		dp1[i][2]=max(dp1[i][2],dp1[i-1][2]+children[i].v2);
		dp1[i][1]=max(dp1[i][1],dp1[i-1][0]+children[i].v3);
		dp1[i][2]=max(dp1[i][2],dp1[i-1][1]+children[i].v3);
	}
	dp[u][0]=max(dp1[children.size()-1][0],dp1[children.size()-1][2]);
	dp[u][1]=dp1[children.size()-1][1];
}
int main()
{
	cin>>n;
	for(int 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});
	}
	dfs(1,0);
	cout<<dp[1][0]<<endl;
return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=1;i<children.size();i++)
      |              ~^~~~~~~~~~~~~~~~

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