Submission #655827

#	Time	Username	Problem	Language	Result	Execution time	Memory
655827		as111	Network (BOI15_net)	C++17	0 / 100	7 ms	12048 KiB

net

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#define MAXN 500000
using namespace std;
struct Path {
	vector<int> path;
	Path(vector<int> p) {
		path = p;
	}
	int size() {
		return (int)path.size();
	}
};
set<int> leafs; // leaf nodes sorted by depth
int mxleaf[MAXN + 1]; // max number leaf in any path for each as root
vector<Path> paths;
set<pair<int, int>> erase; // nodes to delete
vector<int> adj[MAXN + 1];
int root;

struct c {
	bool operator() (Path x, Path y) {
		return x.size() < y.size();
	}
};
int dfs1(int y, int x) {
	int count = 0;
	if (leafs.count(x))count++;
	int mx = 0;
	for (int e : adj[x]) {
		if (e == y)continue;
		int c = dfs1(x, e);
		count += c;
		mx = max(mx, c);
	}
	mxleaf[x] = max(mx, (int)leafs.size() - count);
	return count;
}
vector<int> dfs2(int y, int x) {
	vector<int> total;
	for (int e : adj[x]) {
		if (e == y)continue;
		vector<int> child = dfs2(x, e);
		for (int l : child) total.push_back(l);
	}
	if (leafs.count(x)) total.push_back(x);
	return total;
}
int main() {
	int N;
	cin >> N;
	for (int i = 1; i < N; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= N; i++) {
		if (adj[i].size() == 1) {
			leafs.insert(i);
		}
	}
	dfs1(0, 1);
	root = 1;
	for (int i = 1; i <= N; i++) {
		if (mxleaf[i] < mxleaf[root]) root = i;
	}
	int total = 0;
	priority_queue<Path, vector<Path>, c> pq;
	
	for (int e : adj[root]) {
		Path childpath(dfs2(root, e));
		total += (int)childpath.size();
		paths.push_back(childpath);
		pq.push(childpath);
	}
	
	cout << (total + 1) / 2 << endl;
	while (!pq.empty()) {
		Path fir = pq.top(); pq.pop();
		
		if (pq.empty()) {
			cout << fir.path[0] << " " << root;
			break;
		}
		Path sec = pq.top(); pq.pop();
		int fs = fir.size();
		int ss = sec.size();
		int mn = min(fs, ss);
		for (int i = 1; i <= mn; i++) {
			cout << fir.path[fs - i] << " " << sec.path[ss - i] << endl;
			fir.path.pop_back();
			sec.path.pop_back();
		}
		if (fir.size()>0) {
			pq.push(fir);
		}
		if(sec.size() > 0) {
			pq.push(sec);
		}
	}
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37