Submission #1168921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168921		Muhammet	Beads and wires (APIO14_beads)	C++20	100 / 100	133 ms	46832 KiB

beads

#include "bits/stdc++.h"
 
using namespace std;
 
#define ff first
#define ss second
#define ll long long
#define SZ(s) (int)s.size()
 
const int N = 2e5 + 5;
 
vector <pair <int, int>> v[N];
 
ll dp[N][2], ans = 0, dp1[N][2], vis[N], kk[N];
 
multiset <ll> st[N];
 
void f(int x, int y) {
	vector <pair <int, int>> v1;
	ll w = 0, s = 0, s1 = 0;
	for(auto i : v[x]) {
		if(i.ff == y) {
			w = i.ss;
			continue;
		}
		f(i.ff, x);
		v1.push_back({i.ff, i.ss});
		s += max(dp[i.ff][0], dp[i.ff][1]);
	}
	dp[x][0] = dp[x][1] = s;
	for(int i = 0; i < SZ(v1); i++) {
		int a = v1[i].ff, wa = v1[i].ss;
		dp[x][1] = max(dp[x][1], w + s - max(dp[a][0], dp[a][1]) + dp[a][0] + wa);
	}
}
 
void fn(int x, int y, int ww) {
	if(!vis[y]) {
		for(auto [i, w] : v[y]) {
			kk[y] += max(dp1[i][0], dp1[i][1]);
			st[y].insert(dp1[i][0] + w - max(dp1[i][0], dp1[i][1]));
		}
		while(SZ(st[y]) > 2) st[y].erase(st[y].begin());
		vis[y] = true;
	}
	bool tr = 0;
	dp1[y][1] = dp1[y][0] = kk[y] - max(dp1[x][0], dp1[x][1]);
	if(st[y].find(dp1[x][0] + ww - max(dp1[x][0], dp1[x][1])) != st[y].end()) st[y].erase(st[y].find(dp1[x][0] + ww - max(dp1[x][0], dp1[x][1]))), tr = 1;
	if(SZ(st[y]) > 0) dp1[y][1] = max(dp1[y][1], ww + kk[y] - max(dp1[x][0], dp1[x][1]) + *st[y].rbegin());
	if(tr == 1) st[y].insert(dp1[x][0] + ww - max(dp1[x][0], dp1[x][1]));
	ll k = 0;
	for(auto [i, w] : v[x]) {
		k += max(dp1[i][0], dp1[i][1]);
	}
	ans = max(ans, k);
	for(auto [i, w] : v[x]) {
		if(i != y) fn(i, x, w);
	}
	dp1[y][0] = dp[y][0];
	dp1[y][1] = dp[y][1];
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
 
	int n;
	cin >> n;
	for(int i = 1; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({b, c});
		v[b].push_back({a, c});
	}
 
	f(1, 0);
	for(int i = 1; i <= n; i++) {
		dp1[i][0] = dp[i][0];
		dp1[i][1] = dp[i][1];
	}
	fn(1, 0, 0);
 
	cout << ans;
 
	return 0;
}

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