Submission #110934

#	Time	Username	Problem	Language	Result	Execution time	Memory
110934		zscoder	Beads and wires (APIO14_beads)	C++17	28 / 100	1056 ms	8320 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);

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';
}

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;
	for(int i=0;i<n;i++)
	{
		dfs(i,-1);
		ans=max(ans,dp[i][0]);
	}
	cout<<ans<<'\n';
}

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