Submission #155038

#	Time	Username	Problem	Language	Result	Execution time	Memory
155038		junodeveloper	Network (BOI15_net)	C++14	100 / 100	710 ms	116472 KiB

net

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=500000;
int n,D[maxn+10][2];
vector<int> adj[maxn+10];
vector<pii> res;
void solve(int p,int u) {
	vector<int> ones,twos;
	for(auto& it:adj[u]) {
		if(it==p) continue;
		solve(u,it);
		if(D[it][1]) twos.push_back(it);
		else if(D[it][0]) ones.push_back(it);
	}
	while(sz(twos)>=2) {
		res.push_back({D[twos.back()][1],D[twos[sz(twos)-2]][1]});
		ones.push_back(twos.back());
		ones.push_back(twos[sz(twos)-2]);
		twos.pop_back();twos.pop_back();
	}
	if(!twos.empty()&&ones.empty()) {
		D[u][0]=D[twos[0]][0];
		D[u][1]=D[twos[0]][1];
		return;
	}
	if(!twos.empty()) {
		res.push_back({D[twos.back()][1],D[ones.back()][0]});
		ones.pop_back();ones.push_back(twos.back());
		twos.pop_back();
	}
	while(sz(ones)>=3) {
		res.push_back({D[ones.back()][0],D[ones[sz(ones)-2]][0]});
		ones.pop_back();ones.pop_back();
	}
	if(u==p) {
		if(sz(ones)==1) res.push_back({u,D[ones.back()][0]});
		else if(sz(ones)==2) res.push_back({D[ones.back()][0],D[ones[sz(ones)-2]][0]});
	} else if(sz(adj[u])==1) D[u][0]=u;
	else {
		if(sz(ones)>=1) D[u][0]=D[ones[0]][0];
		if(sz(ones)>=2) D[u][1]=D[ones[1]][0];
	}
}
int main() {
	scanf("%d",&n);
	int i;
	for(i=0;i+1<n;i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int rt=-1;
	for(i=1;i<=n;i++) if(sz(adj[i])!=1) rt=i;
	solve(rt,rt);
	printf("%d\n",sz(res));
	for(auto& it:res) printf("%d %d\n",it.fi,it.se);
	return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
net.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~

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