Submission #656093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
656093	2022-11-06T09:43:54 Z	Makarooni	Network (BOI15_net)	C++17	0 / 100	19 ms	35556 KB

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;
		}
	}
	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));
	}
	if(sz(st[0]) != 0)
		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 || par[root] == w){
		if(root == 1 && w == 2)
			W = 3;
		else if(root == 2 && w == 1)
			W = 3;
		else if(root == 1)
			W = 2;
		else if(root == 2)
			W = 1;
		else
			W = 1;
	}
	else
		W = root;
	cout << w << " " << W;
}

Subtask #1

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	35540 KB	Output is correct
2	Correct	17 ms	35440 KB	Output is correct
3	Correct	17 ms	35556 KB	Output is correct
4	Correct	16 ms	35540 KB	Output is correct
5	Correct	17 ms	35512 KB	Output is correct
6	Correct	17 ms	35552 KB	Output is correct
7	Correct	18 ms	35504 KB	Output is correct
8	Correct	17 ms	35476 KB	Output is correct
9	Correct	17 ms	35448 KB	Output is correct
10	Correct	17 ms	35464 KB	Output is correct
11	Correct	17 ms	35552 KB	Output is correct
12	Correct	18 ms	35532 KB	Output is correct
13	Correct	17 ms	35556 KB	Output is correct
14	Correct	19 ms	35464 KB	Output is correct
15	Correct	17 ms	35536 KB	Output is correct
16	Correct	17 ms	35448 KB	Output is correct
17	Incorrect	17 ms	35496 KB	Breaking single line is causing network to disconnect.
18	Halted	0 ms	0 KB	-

Subtask #2

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	35540 KB	Output is correct
2	Correct	17 ms	35440 KB	Output is correct
3	Correct	17 ms	35556 KB	Output is correct
4	Correct	16 ms	35540 KB	Output is correct
5	Correct	17 ms	35512 KB	Output is correct
6	Correct	17 ms	35552 KB	Output is correct
7	Correct	18 ms	35504 KB	Output is correct
8	Correct	17 ms	35476 KB	Output is correct
9	Correct	17 ms	35448 KB	Output is correct
10	Correct	17 ms	35464 KB	Output is correct
11	Correct	17 ms	35552 KB	Output is correct
12	Correct	18 ms	35532 KB	Output is correct
13	Correct	17 ms	35556 KB	Output is correct
14	Correct	19 ms	35464 KB	Output is correct
15	Correct	17 ms	35536 KB	Output is correct
16	Correct	17 ms	35448 KB	Output is correct
17	Incorrect	17 ms	35496 KB	Breaking single line is causing network to disconnect.
18	Halted	0 ms	0 KB	-

Subtask #3

0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	35540 KB	Output is correct
2	Correct	17 ms	35440 KB	Output is correct
3	Correct	17 ms	35556 KB	Output is correct
4	Correct	16 ms	35540 KB	Output is correct
5	Correct	17 ms	35512 KB	Output is correct
6	Correct	17 ms	35552 KB	Output is correct
7	Correct	18 ms	35504 KB	Output is correct
8	Correct	17 ms	35476 KB	Output is correct
9	Correct	17 ms	35448 KB	Output is correct
10	Correct	17 ms	35464 KB	Output is correct
11	Correct	17 ms	35552 KB	Output is correct
12	Correct	18 ms	35532 KB	Output is correct
13	Correct	17 ms	35556 KB	Output is correct
14	Correct	19 ms	35464 KB	Output is correct
15	Correct	17 ms	35536 KB	Output is correct
16	Correct	17 ms	35448 KB	Output is correct
17	Incorrect	17 ms	35496 KB	Breaking single line is causing network to disconnect.
18	Halted	0 ms	0 KB	-