oj.uz

Submission #723386

# Submission time Handle Problem Language Result Execution time Memory
723386 2023-04-13T16:30:21 Z gagik_2007 Village (BOI20_village) C++17
6 / 100
 141 ms 139724 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll M = 307;
const ll LG = 31;
ll n, m, k;
vector<ll>g[N];
vector<ll>res_mn, res_mx;
ll ans_mn = 0, ans_mx = 0;
bool used[N];
ll sz[N];
stack<ll>st[N];
bool useds[N];

bool comp(ll x, ll y) {
	return st[x].size() < st[y].size();
}

multiset<ll, decltype(&comp)> s(&comp);

void dfs(ll v, ll par = -1) {
	for (ll to : g[v]) {
		if (to != par) {
			dfs(to, v);
		}
	}
	vector<ll>leaves;
	for (ll to : g[v]) {
		if (to != par) {
			if (!used[to]) {
				leaves.push_back(to);
			}
		}
	}
	if (leaves.size() != 0) {
		ans_mn += leaves.size() * 2;
		res_mn[v] = leaves[0];
		for (ll i = 0; i < leaves.size() - 1; i++) {
			res_mn[leaves[i]] = leaves[i + 1];
		}
		res_mn[leaves[leaves.size() - 1]] = v;
		for (ll to : leaves) {
			used[to] = true;
		}
		used[v] = true;
	}
}

void calc_sz(ll v, ll par = -1) {
	sz[v] = 1;
	for (ll to : g[v]) {
		if (to != par) {
			calc_sz(to, v);
			sz[v] += sz[to];
		}
	}
	if (par != -1) {
		ans_mx += 2 * min(ll(sz[v]), n - sz[v]);
	}
}

ll centroid(ll v, ll par = -1) {
	for (ll to : g[v]) {
		if (to != par) {
			if (sz[to] > n / 2) {
				return centroid(to, v);
			}
		}
	}
	return v;
}

void inch_tenum_es_qci_stacki_mej(ll v, ll par, ll cur) {
	if (!useds[v])st[cur].push(v);
	for (ll to : g[v]) {
		if (to != par) {
			inch_tenum_es_qci_stacki_mej(to, v, cur);
		}
	}
}

int main() {
	//freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	ll leaf = 0;
	for (ll i = 0; i < n - 1; i++) {
		ll x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (ll v = 1; v <= n; v++) {
		if (g[v].size() == 1) {
			leaf = v;
			break;
		}
	}
	ll root = g[leaf][0];
	res_mn.resize(n + 1, 0);
	res_mx.resize(n + 1, 0);
	dfs(root);
	calc_sz(1);
	ll c = centroid(1);
	if (n % 2 != 0) {
		ll cur_stack = 0;
		for (ll to : g[c]) {
			inch_tenum_es_qci_stacki_mej(to, c, cur_stack++);
		}
		ll maxim = 0;
		for (ll i = 0; i < cur_stack; i++) {
			if (comp(maxim, i)) {
				maxim = i;
			}
			//cout << i << ": " << st[i].size() << endl;
		}
		ll v1 = st[maxim].top();
		st[maxim].pop();
		ll smaxim = 0;
		for (ll i = 0; i < cur_stack; i++) {
			if (comp(smaxim, i) && i != maxim) {
				smaxim = i;
			}
			//cout << i << ": " << st[i].size() << endl;
		}
		ll v2 = st[smaxim].top();
		st[smaxim].pop();
		res_mx[c] = v1;
		res_mx[v1] = v2;
		res_mx[v2] = c;
		useds[c] = useds[v2] = useds[v1] = true;
		for (ll i = 0; i < cur_stack; i++) {
			while (!st[i].empty()) {
				st[i].pop();
			}
		}
	}
	ll cur_stack = 0;
	for (ll to : g[c]) {
		inch_tenum_es_qci_stacki_mej(to, c, cur_stack++);
	}
	ll minim = cur_stack;
	if (!useds[c]) {
		st[minim].push(c);
		cur_stack++;
	}
	for (ll i = 0; i < cur_stack; i++) {
		if(st[i].size()!=0)s.insert(i);
	}
	while (!s.empty()) {
		//cout << s.size() << endl;
		ll bg = *s.rbegin();
		s.erase(--s.end());
		ll sbg = *s.rbegin();
		s.erase(--s.end());
		ll v1 = st[bg].top();
		ll v2 = st[sbg].top();
		res_mx[v1] = v2;
		res_mx[v2] = v1;
		st[bg].pop();
		st[sbg].pop();
		if (st[bg].size() != 0) {
			s.insert(bg);
		}
		if (st[sbg].size() != 0) {
			s.insert(sbg);
		}
		//cout << bg << " " << sbg << endl;
	}
	cout << ans_mn + 1 << " " << ans_mx << endl;
	for (ll v = 1; v <= n; v++) {
		cout << res_mn[v] << " ";
	}
	cout << endl;
	for (ll v = 1; v <= n; v++) {
		cout << res_mx[v] << " ";
	}
	cout << endl;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

Compilation message

Village.cpp: In function 'void dfs(ll, ll)':
Village.cpp:67:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (ll i = 0; i < leaves.size() - 1; i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 92 ms 139596 KB Partially correct
2 Partially correct 110 ms 139648 KB Partially correct
3 Partially correct 104 ms 139536 KB Partially correct
4 Partially correct 89 ms 139592 KB Partially correct
5 Partially correct 97 ms 139620 KB Partially correct
6 Partially correct 102 ms 139540 KB Partially correct
7 Partially correct 85 ms 139596 KB Partially correct
8 Partially correct 108 ms 139556 KB Partially correct
9 Partially correct 108 ms 139588 KB Partially correct
10 Partially correct 91 ms 139640 KB Partially correct
11 Partially correct 106 ms 139660 KB Partially correct
12 Partially correct 107 ms 139596 KB Partially correct
13 Partially correct 96 ms 139604 KB Partially correct
14 Partially correct 106 ms 139600 KB Partially correct
15 Partially correct 104 ms 139556 KB Partially correct
16 Partially correct 104 ms 139576 KB Partially correct
17 Partially correct 141 ms 139628 KB Partially correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Partially correct 85 ms 139632 KB Partially correct
2 Partially correct 106 ms 139640 KB Partially correct
3 Partially correct 98 ms 139564 KB Partially correct
4 Partially correct 85 ms 139652 KB Partially correct
5 Incorrect 111 ms 139724 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 92 ms 139596 KB Partially correct
2 Partially correct 110 ms 139648 KB Partially correct
3 Partially correct 104 ms 139536 KB Partially correct
4 Partially correct 89 ms 139592 KB Partially correct
5 Partially correct 97 ms 139620 KB Partially correct
6 Partially correct 102 ms 139540 KB Partially correct
7 Partially correct 85 ms 139596 KB Partially correct
8 Partially correct 108 ms 139556 KB Partially correct
9 Partially correct 108 ms 139588 KB Partially correct
10 Partially correct 91 ms 139640 KB Partially correct
11 Partially correct 106 ms 139660 KB Partially correct
12 Partially correct 107 ms 139596 KB Partially correct
13 Partially correct 96 ms 139604 KB Partially correct
14 Partially correct 106 ms 139600 KB Partially correct
15 Partially correct 104 ms 139556 KB Partially correct
16 Partially correct 104 ms 139576 KB Partially correct
17 Partially correct 141 ms 139628 KB Partially correct
18 Partially correct 85 ms 139632 KB Partially correct
19 Partially correct 106 ms 139640 KB Partially correct
20 Partially correct 98 ms 139564 KB Partially correct
21 Partially correct 85 ms 139652 KB Partially correct
22 Incorrect 111 ms 139724 KB Output isn't correct
23 Halted 0 ms 0 KB -