Submission #1002079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002079		Tob	Beads and wires (APIO14_beads)	C++14	100 / 100	119 ms	32444 KiB

beads

#include <bits/stdc++.h>
 
#define ll long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
 
using namespace std;
 
typedef pair <int, int> pii;
 
const int N = 2e5 + 7, inf = 2e9;
 
int n;
int dp[N][4];
vector <pii> adj[N];
 
void Upd(int& mx, int& mx2, int x) {
	if (x >= mx) {mx2 = mx; mx = x;}
	else if (x > mx2) mx2 = x;
}
 
void dfs(int x, int p = 0) {
	int siz = adj[x].size(), sum = 0, sum2 = 0, mxa = 0, mx = -inf, mx2 = -inf;
	vector <int> v, pre(siz+2, -inf), suf(siz+2, -inf);
	for (int i = 0; i < siz; i++) {
		pre[i+1] = pre[i];
		auto it = adj[x][i];
		if (it.F == p) continue;
		dfs(it.F, x);
		int X = max(dp[it.F][2], dp[it.F][3] + it.S);
		int Y = max(dp[it.F][0], dp[it.F][1] + it.S);
		int Z = dp[it.F][2] + it.S - X;
//		cout << it.F << " " << Z << "\n";
		pre[i+1] = max(pre[i+1], Z);
		suf[i+1] = Z;
		sum += X;
		sum2 += Y;
		mx = max(mx, dp[it.F][0] + it.S - X);
		mx2 = max(mx2, dp[it.F][2] + it.S - X);
		mxa = max(mxa, Y - X);
		v.pb(dp[it.F][2] + it.S - X);
	}
	int mx3 = 0;
	for (int i = siz-1; i >= 0; i--) {
		auto it = adj[x][i];
		suf[i+1] = max(suf[i+1], suf[i+2]);
		if (it.F == p) continue;
		int X = max(dp[it.F][2], dp[it.F][3] + it.S);
		mx3 = max(mx3, dp[it.F][0] - X + it.S + max(pre[i], suf[i+2]));
//		cout << i << " " << it.F << " " << pre[i] << " " << suf[i+2] << "\n";
	}
//	cout << "\n";
	
	dp[x][0] = sum + mxa;
	if (v.size() > 1) dp[x][0] = max(dp[x][0], sum + mx3);
	dp[x][1] = sum + mx;
	dp[x][2] = sum;
	dp[x][3] = sum + mx2;
	if (v.empty()) dp[x][1] = dp[x][3] = -inf;
	
//	cout << sum << " " << mxa << "\n";
//	cout << x << " -> " << dp[x][0] << " " << dp[x][1] << " " << dp[x][2] << " " << dp[x][3] << "\n";
}
 
int main () {
	FIO;
	cin >> n;
	
	for (int i = 1; i < n; i++) {
		int x, y, w; cin >> x >> y >> w;
		adj[x].pb({y, w});
		adj[y].pb({x, w});
	}
	
	dfs(1);
	
	cout << dp[1][0];
 
	return 0;
}

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