Submission #342735

#	Time	Username	Problem	Language	Result	Execution time	Memory
342735		minoum	Beads and wires (APIO14_beads)	C++17	0 / 100	4 ms	5100 KiB

beads

#include<bits/stdc++.h>
 
using namespace std;
typedef long long int ll;
 
#define ll int
 
const int MAXN = 2e5 + 10, inf = INT_MAX / 4;
int n, dp[3][MAXN], tmp[MAXN], last[MAXN], parw[MAXN], mx[MAXN];
vector <pair<int,int>> adj[MAXN];
 
void dfs(int v, int parv){
	tmp[v] = -inf; dp[0][v] = 0; dp[1][v] = dp[2][v] = -inf;
	for(auto i: adj[v]){
		int u = i.first, w = i.second;
		if(u == parv) continue;
		parw[u] = w;
		dfs(u, v);
		dp[1][v] = max(dp[1][v]+ mx[u], dp[0][v]+parw[v]+w+max(dp[0][u], dp[2][u]));
		dp[2][v] = max(dp[2][v]+mx[u], tmp[v]+w+max(dp[0][u],dp[2][u]));
		tmp[v] = max(tmp[v]+mx[u], dp[0][v]+w+max(dp[0][u],dp[2][u]));
		dp[0][v] += mx[u];
	}
	mx[v] = max(max(dp[0][v], dp[1][v]), dp[2][v]);
	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, w;
		cin >> a >> b >> w; a--; b--;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}
	dfs(0, -1);
	cout << max(dp[0][0],dp[2][0]) << '\n';
	return 0; 
}

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