Submission #1283549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283549		g4yuhg	Network (BOI15_net)	C++20	0 / 100	4 ms	14628 KiB

net

#include<bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 500005
#define LOG 17
using namespace std;

const ll inf = 1e9;

bool ghuy4g;

ll n, r, in[N], out[N], timeDfs, tour[N], sola;
vector<ll> adj[N];

vector<ll> la;

bool is[N];

set<ll> s;

void dfs(ll u, ll parent) {
	in[u] = ++ timeDfs;
	tour[timeDfs] = u;
	for (auto v : adj[u]) {
		if (v == parent) continue;
		dfs(v, u);
	}
	if (adj[u].size() == 1) {
		la.push_back(u);
		is[u] = 1;
		s.insert(in[u]);
		sola ++ ;
	}
	out[u] = timeDfs;
}

vector<pii> res;

ll need[N], first;

void dfs2(ll u, ll parent) {
	vector<ll> vt, vt_la;
	for (auto v : adj[u]) {
		if (v == parent) continue;
		dfs2(v, u);
		if (need[v]) {
			vt.push_back(need[v]);	
		}
		else {
			vt_la.push_back(v);
		}
	}
	if (is[u]) return;
	if (vt.size() % 2 == 0) {
		for (int i = 0; i < vt.size(); i += 2) {
			ll x = vt[i], y = vt[i + 1];
			s.erase(in[x]);
			s.erase(in[y]);
			first = x;
			res.push_back({x, y});
		}
		auto it = s.lower_bound(in[u]);
		if (it == s.end()) {
			//cout << "ngu";
			exit(3);
		}
		ll x = *it;
		if (!(in[u] <= x && x <= out[u])) {
			//cout << "ngu";
			exit(3);
		}
		x = tour[x];
		need[u] = x;
	}
	else {
		for (int i = 0; i < vt.size(); i += 2) {
			if (i == vt.size() - 1){
				if (u == r) {
					if (vt_la.size() == 0) {
						//cout << "ngu";
						exit(3);
					}
					res.push_back({vt[i], vt_la.back()});
					s.erase(in[vt[i]]);
					s.erase(in[vt_la.back()]);
					first = vt[i];
					break;
				}
				need[u] = vt[i];
				break;
			}
			ll x = vt[i], y = vt[i + 1];
			s.erase(in[x]);
			s.erase(in[y]);
			first = x;
			res.push_back({x, y});
		}
	}
}

void solve() {
	//r = 4;
	//cout << "r " << r << endl;
   	dfs(r, r);
   	
   	dfs2(r, r);
   	
   	vector<ll> left;
   	for (auto it : s) left.push_back(tour[it]);
   	
   	//cout << "left: ";
   	for (auto it : left) //cout << it << " ";
   	//cout << endl;
   	
   	for (auto it : res) {
   		//cout << it.fi << " " << it.se << endl;
   	}
   	
   	if (left.size() == 1) {
   		res.push_back({first, left[0]});
   	}
   	else {
	   	for (int i = 0; i < left.size(); i += 2) {
	   		if (left.size() % 2 == 1 && i == left.size() - 1) {
	   			//cout << "la thua " << left[i - 1] << " " << left[i] << endl;
	   			res.push_back({left[i - 1], left[i]});
	   			break;
	   		}
	   		//cout << left[i] << " " << left[i + 1] << endl;
	   		res.push_back({left[i], left[i + 1]});
	   	}
   	}
   	cout << res.size() << endl;// << " == " << (sola + 1) / 2 << endl;
   	for (auto it : res) {
   		cout << it.fi << " " << it.se << endl;
   	}
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
   	cin >> n;
   	for (int i = 1; i <= n - 1; i ++) {
   		ll u, v;
   		cin >> u >> v;
   		adj[u].push_back(v);
   		adj[v].push_back(u);
   	}
   	
   	for (int i = 1; i <= n; i ++) {
   		if (adj[i].size() > 1) {
   			r = i;
   			break;
   		}
   	}
   	solve();
   	
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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