Submission #388171

#	Time	Username	Problem	Language	Result	Execution time	Memory
388171		Keshi	Beads and wires (APIO14_beads)	C++17	100 / 100	367 ms	36852 KiB

beads

//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll n, dp[maxn][2], pd[maxn][2], par[maxn];
vector<pll> g[maxn];
bool vis[maxn];

void dfs(ll v){
	ll mx = -inf;
	vis[v] = 1;
	for(pll u : g[v]){
		if(vis[u.F]) continue;
		dfs(u.F);
		par[u.F] = u.S;
		dp[v][0] += max(dp[u.F][0], dp[u.F][1] + u.S);
		mx = max(mx, dp[u.F][0] + u.S - max(dp[u.F][0], dp[u.F][1] + u.S));
	}
	dp[v][1] = dp[v][0] + mx;
}
void sfd(ll v, ll p = -1){
	vis[v] = 1;
	ll s = 0;
	if(~p) s += max(pd[v][0], pd[v][1] + p);
	vector<pll> vec;
	if(~p) vec.pb(Mp(pd[v][0] + p - max(pd[v][0], pd[v][1] + p), v));
	for(pll u : g[v]){
		if(vis[u.F]) continue;
		s += max(dp[u.F][0], dp[u.F][1] + u.S);
		vec.pb(Mp(dp[u.F][0] + u.S - max(dp[u.F][0], dp[u.F][1] + u.S), u.F));
	}
	sort(all(vec), greater<pll>());
	vec.pb(Mp(-inf, 0));
	for(pll u : g[v]){
		if(vis[u.F]) continue;
		pd[u.F][0] = s - max(dp[u.F][0], dp[u.F][1] + u.S);
		pd[u.F][1] = pd[u.F][0] + (vec[0].S == u.F ? vec[1].F : vec[0].F);
		sfd(u.F, u.S);
	}
	return;
}

int main(){
    fast_io;

	cin >> n;
	for(ll i = 1; i < n; i++){
		ll v, u, c;
		cin >> v >> u >> c;
		g[v].pb(Mp(u, c));
		g[u].pb(Mp(v, c));
	}
	dfs(4);
	fill(vis, vis + n + 1, 0);
	sfd(4);
	ll ans = 0;
	for(ll i = 1; i <= n; i++){
		ans = max(ans, dp[i][0] + max(pd[i][0], pd[i][1] + par[i]));
	}
	cout << ans;

    return 0;
}

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