Submission #670193

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

beads

#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const ll linf = 9e18 + 5;


int n;
const int N = 2e5 + 5;
vector<pair<int, int>> adj[N];

int dp[N][2];


void dfs(int u, int p) {
	vector<int> toinde;
	int desum = 0;
	int pw = 0;

	for (auto e : adj[u]) {
		int v = e.fi;
		int w = e.se;

		if (v != p) {
			dfs(v, u);

	
			int contri = max(dp[v][0], dp[v][1]);
			desum += contri;
			if (dp[v][1] == -1) {
				toinde.pb(dp[v][0] + w);
			}
			else {
				toinde.pb(dp[v][0] + w - contri);
			}
		}
		else {
			pw = w;
		}
	}

	int maxi[2] = {-inf, -inf};
	for (auto x : toinde) {
		if (x > maxi[0]) {
			maxi[1] = maxi[0];
			maxi[0] = x;
		}
		else if (x > maxi[1]) {
			maxi[1] = x;
		}
	}
	
	dp[u][0] = desum;
	if (maxi[1] != -inf) {
		dp[u][0] = max(dp[u][0], desum + maxi[0] + maxi[1]);
	}

	if (maxi[0] != -inf) {
		dp[u][1] = desum + maxi[0] + pw;
	}
	else {
		dp[u][1] = -1;
	}
}

void init() {
}

void input() {
	cin >> n;

	for (int i = 1; i < n; i++) {
		int u, v, c;
		cin >> u >> v >> c;

		adj[u].pb(mp(v, c));
		adj[v].pb(mp(u, c));
	}
}

void solve() {
	dfs(1, 0);

	cout << dp[1][0];
}

void output() {
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int number_of_testcases = 1;
	//cin >> number_of_testcases;
	while (number_of_testcases--) {
		init();

		input();

		solve();

		output();
	}

	return 0;
}

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