Submission #270854

#	Time	Username	Problem	Language	Result	Execution time	Memory
270854		ChrisT	Network (BOI15_net)	C++17	100 / 100	869 ms	89516 KiB

net

#include<bits/stdc++.h>
using namespace std;
const int MN = 5e5 + 2;
vector<int> adj[MN], has[MN]; vector<pair<int,int>> ret;
int tt,sz[MN],cmp[MN],freq[MN],cnt,rt=-1;
void dfs (int cur, int p = -1) {
	int mx = 0;
	for (int i : adj[cur]) if (i != p) {
		dfs(i,cur);
		mx = max(mx,sz[i]);
		sz[cur] += sz[i];
	}
	if (adj[cur].size()>1) {
		mx = max(mx,cnt - sz[cur]);
		if (mx * 2 <= cnt) rt = cur;
	} else ++sz[cur];
}
void go (int cur, int p = -1, int cc = 0) {
	cmp[cur] = cc;
	for (int i : adj[cur]) if (i != p) go(i,cur,cc?:i);
	if (adj[cur].size() == 1) has[cc].push_back(cur),++freq[cc];
}
int main () { 
    int n; scanf ("%d",&n);
    for (int i = 1; i < n; i++) {
		int a,b; scanf ("%d %d",&a,&b);
		adj[a].push_back(b); adj[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) cnt += adj[i].size() == 1;
	dfs(1);
	assert(~rt);
	go(rt);
	set<pair<int,int>,greater<pair<int,int>>> st;
	for (int i = 1; i <= n; i++) if (freq[i]) st.insert({freq[i],i});
	while (!st.empty()) {
		if (st.size() == 1) {
			auto [f,x] = *st.begin();
			ret.emplace_back(has[x].back(),rt);
			st.erase(st.begin());
		} else {
			auto [f,x] = *st.begin(); 
			auto [f2,x2] = *next(st.begin()); 
			ret.emplace_back(has[x].back(),has[x2].back());
			has[x].pop_back(); has[x2].pop_back();
			st.erase(st.begin()); st.erase(st.begin());
			if (--f) st.insert({f,x});
			if (--f2) st.insert({f2,x2});
		}
	}
	printf ("%d\n",(int)ret.size());
	for (auto [u,v] : ret) printf ("%d %d\n",u,v);
    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |     int n; scanf ("%d",&n);
      |            ~~~~~~^~~~~~~~~
net.cpp:26:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |   int a,b; scanf ("%d %d",&a,&b);
      |            ~~~~~~^~~~~~~~~~~~~~~

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