Submission #656080

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
656080	2022-11-06T09:29:18 Z	Makarooni	Network (BOI15_net)	C++14	0 / 100	20 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;
		}
	}
	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));
	}
	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;
}

Compilation message

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	35540 KB	Output is correct
2	Correct	18 ms	35540 KB	Output is correct
3	Correct	17 ms	35540 KB	Output is correct
4	Correct	18 ms	35556 KB	Output is correct
5	Correct	20 ms	35504 KB	Output is correct
6	Correct	17 ms	35480 KB	Output is correct
7	Correct	17 ms	35556 KB	Output is correct
8	Correct	19 ms	35540 KB	Output is correct
9	Correct	16 ms	35512 KB	Output is correct
10	Correct	17 ms	35540 KB	Output is correct
11	Correct	17 ms	35540 KB	Output is correct
12	Correct	18 ms	35540 KB	Output is correct
13	Correct	19 ms	35540 KB	Output is correct
14	Correct	18 ms	35540 KB	Output is correct
15	Correct	19 ms	35484 KB	Output is correct
16	Correct	18 ms	35540 KB	Output is correct
17	Incorrect	18 ms	35440 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	18 ms	35540 KB	Output is correct
2	Correct	18 ms	35540 KB	Output is correct
3	Correct	17 ms	35540 KB	Output is correct
4	Correct	18 ms	35556 KB	Output is correct
5	Correct	20 ms	35504 KB	Output is correct
6	Correct	17 ms	35480 KB	Output is correct
7	Correct	17 ms	35556 KB	Output is correct
8	Correct	19 ms	35540 KB	Output is correct
9	Correct	16 ms	35512 KB	Output is correct
10	Correct	17 ms	35540 KB	Output is correct
11	Correct	17 ms	35540 KB	Output is correct
12	Correct	18 ms	35540 KB	Output is correct
13	Correct	19 ms	35540 KB	Output is correct
14	Correct	18 ms	35540 KB	Output is correct
15	Correct	19 ms	35484 KB	Output is correct
16	Correct	18 ms	35540 KB	Output is correct
17	Incorrect	18 ms	35440 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	18 ms	35540 KB	Output is correct
2	Correct	18 ms	35540 KB	Output is correct
3	Correct	17 ms	35540 KB	Output is correct
4	Correct	18 ms	35556 KB	Output is correct
5	Correct	20 ms	35504 KB	Output is correct
6	Correct	17 ms	35480 KB	Output is correct
7	Correct	17 ms	35556 KB	Output is correct
8	Correct	19 ms	35540 KB	Output is correct
9	Correct	16 ms	35512 KB	Output is correct
10	Correct	17 ms	35540 KB	Output is correct
11	Correct	17 ms	35540 KB	Output is correct
12	Correct	18 ms	35540 KB	Output is correct
13	Correct	19 ms	35540 KB	Output is correct
14	Correct	18 ms	35540 KB	Output is correct
15	Correct	19 ms	35484 KB	Output is correct
16	Correct	18 ms	35540 KB	Output is correct
17	Incorrect	18 ms	35440 KB	Breaking single line is causing network to disconnect.
18	Halted	0 ms	0 KB	-