Submission #139838

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
139838	2019-08-01T14:06:55 Z	Saboon	Network (BOI15_net)	C++14	0 / 100	24 ms	23928 KB

net

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
const int maxn = 5e5 + 10;
 
int par[maxn], sz[maxn];
vector<int> t[maxn];
 
int cnt;
vector<int> a[maxn];
 
void DFS(int v, int par = -1){
	bool leaf = 1;
	for (auto u : t[v]){
		if (u != par){
			DFS(u, v);
			leaf = 0;
		}
		if (par == -1)
			cnt ++;
	}
	if (leaf){
		a[cnt].push_back(v);
	}
}
 
int dfs(int v, int par = -1){
	for (auto u : t[v])
		if (u != par)
			sz[v] += dfs(u, v);
	if (sz[v] == 0)
		sz[v] = 1;
	return sz[v];
}
 
int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++){
		int v, u;
		cin >> v >> u;
		t[v].push_back(u);
		t[u].push_back(v);
	}
	int root;
	for (root = 1; root <= n; root ++)
		if (t[root].size() > 1)
			break;
	dfs(root);
	int v = root, Max = sz[root], parent = -1;
	bool found = 1;
	while (found){
		found = 0;
		for (auto u : t[v]){
			if (u != parent and sz[u] >= Max / 2){
				parent = v;
				v = u;
				found = 1;
				break;
			}
		}
	}
	cerr << "centroid : " << v << endl;
	DFS(v);
	vector<pair<int, int> > ans;
	set<pair<int, int> > s;
	for (int i = 0; i < cnt; i++){
		int k = a[i].size();
		s.insert({-k, i});
	}
	while (!s.empty()){
		if (s.size() == 1){
			int fi = (*s.begin()).second;
			ans.push_back({a[fi].back(), v});
			break;
		}
		int fi = (*s.begin()).second;
		s.erase(s.begin());
		int se = (*s.begin()).second;
		s.erase(s.begin());
		ans.push_back({a[fi].back(), a[se].back()});
		a[fi].pop_back();
		if (!a[fi].empty())
			s.insert({-a[fi].size(), fi});
		a[se].pop_back();
		if (!a[se].empty())
			s.insert({-a[se].size(), se});
	}
	cout << ans.size() << endl;
	for (auto it : ans)
		cout << it.first << " " << it.second << endl;
}

Subtask #1

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	24 ms	23928 KB	Expected integer, but "centroid" found
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	24 ms	23928 KB	Expected integer, but "centroid" found
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	24 ms	23928 KB	Expected integer, but "centroid" found
2	Halted	0 ms	0 KB	-