Submission #517037

#	Time	Username	Problem	Language	Result	Execution time	Memory
517037		haxorman	Beads and wires (APIO14_beads)	C++14	0 / 100	3 ms	5024 KiB

beads

#include <bits/stdc++.h>
using namespace std;

const int mxN = 2e5 + 7;

int n;
vector<int> cur_seg;
vector<pair<int,int>> graph[mxN];
int dp[mxN], p[mxN];
bool vis[mxN];
map<pair<int,int>,bool> used;
 
void dfs(int u, int par) {
	dp[u] = 1;
	p[u] = par;
 
	for (auto pr : graph[u]) {
		int v = pr.first;
		if (!vis[v] && v != par) {
			dfs(v, u);
			dp[u] += dp[v];
		}
	}
 
	cur_seg.push_back(u);
}
 
int find_centroid(int x) {
	cur_seg.clear();
	dfs(x, -1);
 
	for (int u : cur_seg) {
		int max_subtree = cur_seg.size() - dp[u];
 
		for (auto pr : graph[u]) {
			int v = pr.first;
			if (v != p[u] && !vis[v]) {
				max_subtree = max(max_subtree, dp[v]);
			}
		}
 
		if (max_subtree <= cur_seg.size() / 2) {
			return u;
		}
	}
 
	return x;
}
 
int ans = 0;
 
void decompose(int x) {
	int c = find_centroid(x);
	vis[c] = true;
	
	pair<int,int> max1 = {0, 0}, max2 = {0, 0};
	for (auto pr : graph[c]) {
		int v = pr.first, w = pr.second;

		if (!vis[v] && !used[{c, v}]) {
			if (w > max1.first) {
				max1 = {w, v};
			}
			else if (w > max2.first) {
				max2 = {w, v};
			}
		}
	}

	used[{c, max1.second}] = used[{max1.second, c}] = true;
	used[{c, max2.second}] = used[{max2.second, c}] = true;

	ans += max1.first + max2.first;

	for (auto pr : graph[c]) {
		int v = pr.first;
		if (!vis[v]) {
			decompose(v);
		}
	}
}
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;

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

		graph[u].push_back({v, w});
		graph[v].push_back({u, w});
	}

	decompose(1);
	cout << ans << "\n";
}

Compilation message (stderr)

beads.cpp: In function 'int find_centroid(int)':
beads.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   if (max_subtree <= cur_seg.size() / 2) {
      |       ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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