Submission #343937

#	Time	Username	Problem	Language	Result	Execution time	Memory
343937		minoum	Beads and wires (APIO14_beads)	C++17	100 / 100	231 ms	36700 KiB

beads

#include<bits/stdc++.h>
 
using namespace std;
typedef long long int ll;
 
const int MAXN = 2e5 + 10;
const ll inf = (ll)1e15;
ll n, dp[5][MAXN], tmp[5][MAXN], parw[MAXN];
vector <pair<int,ll>> adj[MAXN];
 
void dfs(int v, int parv){
	tmp[0][v] = tmp[1][v] = dp[1][v] = dp[2][v] = dp[3][v] = dp[4][v] = -inf;
	dp[0][v] = 0;
	for(auto i: adj[v]){
		int u = i.first; ll w = i.second;
		if(u == parv) continue;
		parw[u] = w;
		dfs(u, v);
		ll l0 = dp[0][v], l1 = dp[1][v], l2 = dp[2][v], l3 = dp[3][v], l4 = dp[4][v];
		dp[0][v] += max(dp[0][u], dp[2][u]);
		dp[1][v] = max(l1+max(dp[0][u],dp[2][u]),l0+max(max(dp[0][u],dp[1][u]),max(dp[3][u], dp[4][u])));
		dp[2][v] = max(l2+max(dp[0][u],dp[2][u]),l0+parw[v]+w+dp[0][u]);
		dp[3][v] = max(l3+max(dp[0][u],dp[2][u]),l0+parw[v]+w+max(max(dp[0][u],dp[1][u]),dp[4][u]));
		dp[4][v] = max(tmp[0][v]+max(max(dp[0][u],dp[1][u]),dp[4][u])+w,tmp[1][v]+dp[0][u]+w);
		dp[4][v] = max(dp[4][v], l4+max(dp[0][u],dp[2][u]));
		tmp[0][v] = max(tmp[0][v]+max(dp[0][u],dp[2][u]),l0+dp[0][u]+w);
		tmp[1][v] = max(tmp[1][v]+max(dp[0][u],dp[2][u]),l0+max(max(dp[0][u],dp[1][u]),dp[4][u])+w);
	}
	return;
}
 
int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;	
	for(int i = 0; i < n-1; i++){
		int a, b; ll w;
		cin >> a >> b >> w; a--; b--;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}
	dfs(0, -1);
	cout << max(max(dp[0][0], dp[1][0]),dp[4][0]) << '\n';
	return 0; 
}

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