제출 #1274647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274647		behesht	Network (BOI15_net)	C++20	100 / 100	645 ms	98068 KiB

net

#include <bits/stdc++.h>
 
#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define arr(x)               array <ll, x>
#define ld                   long double
#define ll                   long long
#define int                  long long
#define pb                   push_back
#define endl                 '\n'
#define lc                   v << 1
#define rc                   v << 1 | 1
 
using namespace std;
 
const int INF = 1e9 + 24 + (34 / 10); // 34 ---> 35
const int MAXN = 5e5 + 24 + (34 / 10); // 34 ---> 35
 
vector <int> adj[MAXN];
vector <arr(2)> ans;
int r;
 
bool cmp(vector <int> a, vector <int> b){
	return a.size() > b.size();
}
 
void merge(vector <vector <int>> a){
 
	while(!a.empty() && (a.back()).empty())
		a.pop_back();
 
	int n = a.size();
 
	// for(auto x : a){
	// 	for(auto v : x)
	// 		cout << v + 1 << " ";
	// 	cout << endl;
	// }
	// cout << endl;
	
	for(int i = 0; i < 2 * n; i += 2){
 
		int x = i % n, y = (i + 1) % n;
 
		if(a[x].empty() || a[y].empty()){
			i--;
			continue;
		}
 
		ans.pb({a[x].back(), a[y].back()});
		a[x].pop_back();
		a[y].pop_back();
	}
}
 
vector <int> dfs(int u, int p){
 
	vector <vector <int>> child;
	vector <int> res;
	
	if(u != r && adj[u].size() == 1){
		res.pb(u);
		return res;
	}
 
	int cnt = 0;
 
	for(auto v : adj[u]){
		if(v != p){
			child.pb(dfs(v, u));
			cnt += (child.back()).size();
		}
	}
 
	// d1(u + 1);
 
	// for(auto x : child){
	// 	for(auto v : x)
	// 		cout << v + 1 << " ";
		
	// 	cout << endl;
	// }
 
	sort(child.begin(), child.end(), cmp);
 
	if(cnt & 1){
		res.pb((child[0]).back());
		(child[0]).pop_back();
	}
 
	else if(child.size() == 1){
		res = child.back();
		child.pop_back();
	}
 
	else{
		res.pb((child[0]).back());
		res.pb((child[1]).back());
 
		(child[0]).pop_back();
		(child[1]).pop_back();
	}
 
	// d1(u + 1);
	// for(auto v : res)
	// 	cout << v + 1 << " ";
	// cout << endl;
 
	sort(child.begin(), child.end(), cmp);
	merge(child);
 
	return res;
}
 
signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int n;
	cin >> n;
 
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
 
		u--;
		v--;
 
		adj[u].pb(v);
		adj[v].pb(u);
	}
 
	for(int i = 0; i < n; i++)
		if(adj[i].size() > 1)
			r = i;
 
	vector <int> eli = dfs(r, r);
 
	// d1(r);
	if(eli.size() == 1){
 
		if(r != adj[eli[0]][0])
			ans.pb({r, eli[0]});
		
		else{
			for(auto v : adj[r])
				if(v != eli[0] && v != adj[eli[0]][0]){
					ans.pb({eli[0], v});
					break;
				}
		}
	}
 
	else 
		ans.pb({eli[0], eli[1]});
 
	cout << ans.size() << endl;
 
	for(auto [u, v] : ans)
		cout << u + 1 << " " << v + 1 << endl;
}
 
// Ey To Bahane! :_)))
 
// -------------<3------------- //
/*
Magasan dor shirini: 
 
1. MAXN
2. Input style
3. index or value? Masale In Ast!	
4. MOD 
 
*/

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