Submission #567931

#	Time	Username	Problem	Language	Result	Execution time	Memory
567931		flappybird	Beads and wires (APIO14_beads)	C++17	0 / 100	3 ms	5060 KiB

beads

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<pii> adj[MAX];
ll X[MAX];
ll dp1[MAX];
ll dp2[MAX];
void dfs(int x, int p = 0) { for (auto& [v, c] : adj[x]) if (v != p) X[v] = c, dfs(v, x); }
void calc(int x, int p = 0) {
	ll mx, mx2;
	mx = mx2 = -INF;
	ll sum = 0;
	for (auto& [v, c] : adj[x]) if (v != p) {
		calc(v, x);
		sum += dp1[v];
		ll dif = dp2[v] + X[v] - dp1[v];
		if (mx2 < dif) mx2 = dif;
		if (mx2 > mx) swap(mx, mx2);
	}
	dp1[x] = max(0ll, X[x] + sum + mx);
	dp2[x] = max(0ll, sum + mx + mx2);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	int i;
	int a, b, c;
	for (i = 1; i < N; i++) {
		cin >> a >> b >> c;
		adj[a].emplace_back(b, c);
		adj[b].emplace_back(a, c);
	}
	dfs(1);
	calc(1);
	cout << dp2[1] << Ln;
}

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