Submission #656056

#	Time	Username	Problem	Language	Result	Execution time	Memory
656056		Makarooni	Network (BOI15_net)	C++17	0 / 100	20 ms	35456 KiB

net

/* IN THE NAME OF GOD */
/* |\/| /-\ |\| | |\/| /-\ */

#include "bits/stdc++.h"
using namespace std;

#define sz(x) (int)x.size()
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define mr make_pair
//#define int long long
#define pii pair<int, int>
typedef long double ld;
typedef long long ll;

const int N = 5e5 + 10;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;

vector<int> g[N];
int l[N], L, par[N], root;
set<int> le, st[N];

void dfs(int v, int p){
	for(int u : g[v]){
		if(u == p)
			continue;
		dfs(u, v);
		par[u] = v;
		l[v] += l[u];
	}
	if(sz(g[v]) == 1){
		l[v]++;
		L++;
		le.insert(v);
	}
}

void dfs2(int v){
	for(int u : g[v]){
		if(u == par[v])
			continue;
		dfs2(u);
		if(v == root)
			continue;
		if(sz(st[v]) < sz(st[u]))
			st[v].swap(st[u]);
		for(int y : st[u])
			st[v].insert(y);
		st[u].clear();
	}
	if(sz(g[v]) == 1){
		st[v].insert(v);
		le.erase(v);
	}
}

int32_t main(){
	ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	int u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1, 0);
	int mx = 0, sm;
	for(int i = 1; i <= n; i++){
		mx = 0, sm = 0;
		for(int u : g[i]){
			if(u == par[i])
				continue;
			mx = max(mx, l[u]);
			sm += l[u];
		}
		mx = max(mx, L - sm);
		if(mx <= L / 2 && sz(g[i]) >= 2){
			root = i;
			break;
		}
	}
	if(root == 0)
		cout << 2/0;
	dfs2(root);
	st[0] = le;
	l[0] = sz(st[0]);
	set<pii> nomily_cheat_nazan;
	for(int u : g[root]){
		if(u == par[root])
			continue;
		nomily_cheat_nazan.insert(mr(l[u], u));
	}
	nomily_cheat_nazan.insert(mr(sz(st[0]), 0));
	cout << L / 2 + (L % 2 != 0) << endl;
	while(sz(nomily_cheat_nazan) > 1){
		//cout << "$" << sz(nomily_cheat_nazan) << endl;
		auto it = nomily_cheat_nazan.end();
		auto it2 = it;
		it--;
		it2--;
		it2--;
		l[it->S]--;
		l[it2->S]--;
		//cout << "#" << it->S << " " << it2->S << endl;
		cout << *st[it2->S].begin() << " " << *st[it->S].begin() << endl;
		st[it->S].erase(*st[it->S].begin());
		st[it2->S].erase(*st[it2->S].begin());
		if(l[it->S] > 0)
			nomily_cheat_nazan.insert(mr(l[it->S], it->S));
		if(l[it2->S] > 0)
			nomily_cheat_nazan.insert(mr(l[it2->S], it2->S));
		nomily_cheat_nazan.erase(it);
		nomily_cheat_nazan.erase(it2);
		//cout << "!" << sz(nomily_cheat_nazan) << endl;
	}
	if(nomily_cheat_nazan.empty())
		return 0;
	int w = *st[nomily_cheat_nazan.begin()->S].begin(), W;
	if(par[w] == root){
		if(root == 1 && w == 2)
			W = 3;
		else if(root == 1 && w == 1)
			W = 2;
		else if(root == 2 && w == 1)
			W = 3;
		else if(root == 2 && w == 2)
			W = 3;
		else if(root == 1)
			W = 2;
		else if(root == 2)
			W = 1;
		else if(w == 1)
			W = 2;
		else if(w == 2)
			W = 1;
		else
			W = 1;
	}
	else
		W = root;
	cout << w << " " << W;
}

Compilation message (stderr)

net.cpp: In function 'int32_t main()':
net.cpp:89:12: warning: division by zero [-Wdiv-by-zero]
   89 |   cout << 2/0;
      |           ~^~

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