Submission #26421

#	Time	Username	Problem	Language	Result	Execution time	Memory
26421		zscoder	Beads and wires (APIO14_beads)	C++14	100 / 100	273 ms	27748 KiB

beads

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

vector<ii> adj[200001];
ll dp[200001][2];
ll dp2[200001][2];
const ll INF = ll(1e15);

void dfs(int u, int p)
{
	int childcnt=0;
	ll maxi=-INF;
	dp[u][1]=-INF;
	for(int i=0;i<adj[u].size();i++)
	{
		int v=adj[u][i].fi; int w=adj[u][i].se;
		if(v==p) continue;
		childcnt++;
		dfs(v,u);
		dp[u][0]+=max(dp[v][0],dp[v][1]+w);
		maxi=max(maxi,-max(dp[v][0],dp[v][1]+w)+w+dp[v][0]);
	}
	if(childcnt>0) 
	{
		dp[u][1]=maxi+dp[u][0];
	}
	//cerr<<u+1<<' '<<b1<<' '<<b2<<'\n';
	//cerr<<u+1<<' '<<dp[u][0]<<' '<<dp[u][1]<<'\n';
}
ll par[200001];
void dfs2(int u, int p)
{
	//cerr<<u+1<<' '<<dp[u][0]<<' '<<dp[u][1]<<'\n';
	ll maxi1 = -INF; ll maxi2 = -INF;
	ll idx1 = -1; ll idx2 = -1;
	for(int i=0;i<adj[u].size();i++)
	{
		int v=adj[u][i].fi; int w=adj[u][i].se;
		par[v]=w;
		if(v==p) continue;
		ll val = -max(dp[v][0],dp[v][1]+w)+w+dp[v][0];
		if(val>maxi1)
		{
			maxi2=maxi1;
			idx2=idx1;
			maxi1=val;
			idx1=i;
		}
		else if(val>maxi2)
		{
			maxi2=val;
			idx2=i;
		}
	}
	if(p!=-1)
	{
		ll val = -max(dp2[u][0],dp2[u][1]+par[u])+par[u]+dp2[u][0];
		if(val>maxi1)
		{
			maxi2=maxi1;
			idx2=idx1;
			idx1=-2;
			maxi1=val;
		}
		else if(val>maxi2)
		{
			maxi2=val;
		}
	}
	for(int i=0;i<adj[u].size();i++)
	{
		int v=adj[u][i].fi; int w=adj[u][i].se;
		if(v==p) continue;
		ll dpu0 = dp[u][0] - max(dp[v][0],dp[v][1]+w);
		ll dpu1 = dpu0 + maxi1;
		if(idx1==i)
		{
			dpu1=dpu0+maxi2;
		}
		ll tmp = dp[v][0];
		//cerr<<u+1<<' '<<v+1<<' '<<dpu0<<' '<<dpu1<<' '<<maxi1<<' '<<maxi2<<'\n';
		dp[v][0] = tmp+max(dpu0,dpu1+w);
		ll maxi = dp[v][1]-tmp;
		maxi=max(maxi,-max(dpu0,dpu1+w)+w+dpu0);
		dp[v][1] = dp[v][0] + maxi;
		dp2[v][0]=dpu0;
		dp2[v][1]=dpu1;
	}
	for(int i=0;i<adj[u].size();i++)
	{
		int v=adj[u][i].fi; int w=adj[u][i].se;
		if(v==p) continue;
		dfs2(v,u);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n-1;i++)
	{
		int u, v; cin>>u>>v;
		int w; cin>>w;
		u--; v--;
		adj[u].pb(mp(v,w));
		adj[v].pb(mp(u,w));
	}
	ll ans = 0;
	dfs(0,-1);
	dfs2(0,-1);
	for(int i=0;i<n;i++) ans=max(ans,dp[i][0]);
	cout<<ans<<'\n';
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[u].size();i++)
              ~^~~~~~~~~~~~~~
beads.cpp: In function 'void dfs2(int, int)':
beads.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[u].size();i++)
              ~^~~~~~~~~~~~~~
beads.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[u].size();i++)
              ~^~~~~~~~~~~~~~
beads.cpp:109:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[u].size();i++)
              ~^~~~~~~~~~~~~~
beads.cpp:111:27: warning: unused variable 'w' [-Wunused-variable]
   int v=adj[u][i].fi; int w=adj[u][i].se;
                           ^
beads.cpp:55:19: warning: variable 'idx2' set but not used [-Wunused-but-set-variable]
  ll idx1 = -1; ll idx2 = -1;
                   ^~~~

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