Submission #31738

#	Time	Username	Problem	Language	Result	Execution time	Memory
31738		kdh9949	Network (BOI15_net)	C++14	100 / 100	1906 ms	128032 KiB

net

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

struct E{ int x, i; };

const int MN = 500005, inf = 1e9;
int n, m, vis[MN], pre[MN], p[MN], s[MN], cn[MN], rep[MN], chk[MN], cnt, low[MN];
vector<int> te[MN], se[MN], lf[MN];
vector<E> e[MN];
priority_queue<pii> pq;

void f(int x, int pv){
	pre[x] = ++cnt;
	low[x] = inf;
	vis[x] = 1;
	for(auto &i : e[x]){
		if(!vis[i.x]){
			te[x].push_back(i.x);
			p[i.x] = x;
			f(i.x, i.i);
		}
		else if(i.i != pv){
			low[x] = min(low[x], pre[i.x]);
		}
	}
}

int g(int x){
	int ret = low[x];
	for(auto &i : te[x]){
		int t = g(i);
		if(t > pre[x]) chk[i] = 1;
		ret = min(ret, t);
	}
	return ret;
}

void h(int x){
	cn[x] = cnt;
	for(auto &i : te[x]) if(!chk[i]) h(i);
}

int sf(int x, int p){
	s[x] = 0;
	for(auto &i : se[x]){
		if(i != p) s[x] += sf(i, x);
	}
	s[x] = max(s[x], 1);
	return s[x];
}

int cf(int x, int p, int t){
	for(auto &i : se[x]){
		if(i != p && s[i] > t / 2) return cf(i, x, t);
	}
	return x;
}

void l(vector<int> &v, int x, int p){
	int fl = 1;
	for(auto &i : se[x]){
		if(i == p) continue;
		fl = 0; l(v, i, x);
	}
	if(fl) v.push_back(x);
}

int main(){
	scanf("%d", &n);
	m = n - 1;
	for(int i = 1, x, y; i <= m; i++){
		scanf("%d%d", &x, &y);
		e[x].push_back({y, i});
		e[y].push_back({x, i});
	}
	f(1, -1);
	g(1);
	//for(int i = 1; i <= n; i++) if(chk[i]) printf("%d - %d\n", i, p[i]);
	cnt = 1; h(1); rep[1] = 1;
	for(int i = 2; i <= n; i++){
		if(chk[i]){
			cnt++;
			h(i);
			rep[cnt] = i;
		}
	}
	for(int i = 2; i <= n; i++){
		if(chk[i]){
			se[cn[p[i]]].push_back(cn[i]);
			se[cn[i]].push_back(cn[p[i]]);
		}
	}
	//puts("--");
	//for(int i = 1; i <= n; i++) printf("%d : %d\n", i, cn[i]);
	if(cnt == 1){ puts("0"); return 0; }
	if(cnt == 2){ printf("1\n%d %d\n", rep[1], rep[2]); return 0; }
	int r;
	for(int i = 1; i <= cnt; i++){
		if(se[i].size() > 1){
			r = cf(i, 0, sf(i, 0));
			break;
		}
	}
	cnt = 0;
	//puts("--");
	for(int i = 0; i < se[r].size(); i++){
		l(lf[i], se[r][i], r);
		pq.push({lf[i].size(), i});
		//printf("%d : %d\n", i, lf[i].size());
		cnt += lf[i].size();
	}
	//puts("--");
	int fl = cnt % 2;
	printf("%d\n", (cnt + 1) / 2);
	while(pq.size() > 1){
		pii a = pq.top(); pq.pop();
		pii b = pq.top(); pq.pop();
		printf("%d %d\n", rep[lf[a.second].back()], rep[lf[b.second].back()]);
		lf[a.second].pop_back();
		if(!fl) lf[b.second].pop_back();
		else fl = 0;
		if(lf[a.second].size()) pq.push({lf[a.second].size(), a.second});
		if(lf[b.second].size()) pq.push({lf[b.second].size(), b.second});
	}
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:107:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < se[r].size(); i++){
                   ^
net.cpp:70:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
net.cpp:73:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^
net.cpp:98:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int r;
      ^

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