Submission #110938

#	Time	Username	Problem	Language	Result	Execution time	Memory
110938		zscoder	Beads and wires (APIO14_beads)	C++17	100 / 100	363 ms	26224 KiB

beads

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ll> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int N = 333333;
vector<ii> adj[N];
int dp[N][2];
const int INF = int(1e9);
int dp2[N][2];

void dfs(int u, int p)
{
	vi pre(2,-INF); pre[0]=0;
	dp[u][0]=dp[u][1]=-INF;
	for(ii X:adj[u])
	{
		int v=X.fi; int w=X.se;
		if(v==p) continue;
		dfs(v,u);
		vi nw(2,-INF);
		nw[0]=max(nw[0],pre[0]+dp[v][0]);
		nw[1]=max(nw[1],pre[1]+dp[v][0]);
		
		nw[0]=max(nw[0],pre[0]+w+dp[v][1]);
		nw[1]=max(nw[1],pre[0]+w+dp[v][0]);
		nw[1]=max(nw[1],pre[1]+w+dp[v][1]);
		pre=nw;
	}
	dp[u][0]=pre[0]; dp[u][1]=pre[1];
	//cerr<<u<<' '<<dp[u][0]<<' '<<dp[u][1]<<'\n';
}

void dfs2(int u, int p)
{
	int sum=dp2[u][0];
	vector<ii> vec;
	vec.pb({dp2[u][1]-dp2[u][0],u});
	for(ii X:adj[u])
	{
		int v=X.fi; int w=X.se;
		if(v==p) continue;
		sum+=max(dp[v][0],dp[v][1]+w);
		int nwval = dp[v][0]+w;
		vec.pb({nwval-max(dp[v][0],dp[v][1]+w),v});
	}
	sort(vec.rbegin(),vec.rend());
	for(ii X:adj[u])
	{
		int v=X.fi; int w=X.se;
		if(v==p) continue;
		//compute dp2[v][0], dp2[v][1]
		dp2[v][1]=-INF;
		sum-=max(dp[v][0],dp[v][1]+w);
		if(w+sum>=0) dp2[v][1]=w+sum;
		dp2[v][0]=sum;
		int largest=vec[0].fi;
		if(vec[0].se==v)
		{
			if(vec.size()<=1) largest=-INF;
			else largest=vec[1].fi;
		}
		dp2[v][0]=max(dp2[v][0],w+sum+largest);
		sum+=max(dp[v][0],dp[v][1]+w);
		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; u--; v--;
		int w; cin>>w;
		adj[u].pb({v,w});
		adj[v].pb({u,w});
	}
	int ans=0;
	dfs(0,-1);
	dp2[0][0]=0; dp2[0][1]=-INF;
	dfs2(0,-1);
	for(int i=0;i<n;i++)
	{
		ans=max(ans,dp[i][0]+dp2[i][0]);
	}
	cout<<ans<<'\n';
}

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