oj.uz

Submission #517037

# Submission time Handle Problem Language Result Execution time Memory
517037 2022-01-22T12:29:59 Z haxorman Beads and wires (APIO14_beads) C++14
0 / 100
 3 ms 5024 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5024 KB Output is correct
2 Incorrect 3 ms 5024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5024 KB Output is correct
2 Incorrect 3 ms 5024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5024 KB Output is correct
2 Incorrect 3 ms 5024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5024 KB Output is correct
2 Incorrect 3 ms 5024 KB Output isn't correct
3 Halted 0 ms 0 KB -