oj.uz

Submission #723227

# Submission time Handle Problem Language Result Execution time Memory
723227 2023-04-13T11:25:36 Z gagik_2007 Village (BOI20_village) C++17
19 / 100
 175 ms 262144 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<int>g[N];
vector<int>res_mn, res_mx;
ll ans_mn = 0, ans_mx = 0;
bool used[N];
int sz[N];
stack<int>st[N];
bool useds[N];

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

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

void dfs(int v, int par = -1) {
	for (int to : g[v]) {
		if (to != par) {
			dfs(to, v);
		}
	}
	vector<int>leaves;
	for (int 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 (int i = 0; i < leaves.size() - 1; i++) {
			res_mn[leaves[i]] = leaves[i + 1];
		}
		res_mn[leaves[leaves.size() - 1]] = v;
		for (int to : leaves) {
			used[to] = true;
		}
		used[v] = true;
	}
}

void calc_sz(int v, int par = -1) {
	sz[v] = 1;
	for (int 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]);
	}
}

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

void inch_tenum_es_qci_stacki_mej(int v, int par, int cur) {
	if (!useds[v])st[cur].push(v);
	for (int 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;
	int leaf = 0;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int v = 1; v <= n; v++) {
		if (g[v].size() == 1) {
			leaf = v;
			break;
		}
	}
	int root = g[leaf][0];
	res_mn.resize(n + 1, 0);
	res_mx.resize(n + 1, 0);
	dfs(root);
	calc_sz(1);
	int c = centroid(1);
	if (n % 2 != 0) {
		int cur_stack = 0;
		for (int to : g[c]) {
			inch_tenum_es_qci_stacki_mej(to, c, cur_stack++);
		}
		int maxim = 0;
		for (int i = 0; i < cur_stack; i++) {
			if (comp(maxim, i)) {
				maxim = i;
			}
			//cout << i << ": " << st[i].size() << endl;
		}
		int v1 = st[maxim].top();
		st[maxim].pop();
		int smaxim = 0;
		for (int i = 0; i < cur_stack; i++) {
			if (comp(smaxim, i) && i != maxim) {
				smaxim = i;
			}
			//cout << i << ": " << st[i].size() << endl;
		}
		int 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 (int i = 0; i < cur_stack; i++) {
			while (!st[i].empty()) {
				st[i].pop();
			}
		}
	}
	int cur_stack = 0;
	for (int to : g[c]) {
		inch_tenum_es_qci_stacki_mej(to, c, cur_stack++);
	}
	int minim = 0;
	for (int i = 0; i < cur_stack; i++) {
		if (comp(i, minim)) {
			minim = i;
		}
		//cout << i << ": " << st[i].size() << endl;
	}
	if (!useds[c])st[minim].push(c);
	for (int i = 0; i < cur_stack; i++) {
		if(st[i].size()!=0)s.insert(i);
	}
	while (!s.empty()) {
		//cout << s.size() << endl;
		int bg = *s.rbegin();
		s.erase(--s.end());
		int sbg = *s.rbegin();
		s.erase(--s.end());
		int v1 = st[bg].top();
		int 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 << " " << ans_mx << endl;
	for (int v = 1; v <= n; v++) {
		cout << res_mn[v] << " ";
	}
	cout << endl;
	for (int 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(int, int)':
Village.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (int i = 0; i < leaves.size() - 1; i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 139544 KB Output is correct
2 Correct 81 ms 139652 KB Output is correct
3 Runtime error 175 ms 262144 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
19.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 139648 KB Output is correct
2 Correct 78 ms 139696 KB Output is correct
3 Correct 78 ms 139680 KB Output is correct
4 Correct 86 ms 139636 KB Output is correct
5 Partially correct 89 ms 139704 KB Partially correct
6 Correct 84 ms 139640 KB Output is correct
7 Correct 83 ms 139776 KB Output is correct
8 Correct 82 ms 139676 KB Output is correct
9 Correct 82 ms 139648 KB Output is correct
10 Correct 81 ms 139724 KB Output is correct
11 Correct 80 ms 139712 KB Output is correct
12 Correct 81 ms 139728 KB Output is correct
13 Correct 80 ms 139708 KB Output is correct
14 Correct 81 ms 139596 KB Output is correct
15 Correct 80 ms 139592 KB Output is correct
16 Correct 80 ms 139668 KB Output is correct
17 Correct 83 ms 139636 KB Output is correct
18 Correct 82 ms 139620 KB Output is correct
19 Correct 83 ms 139724 KB Output is correct
20 Correct 83 ms 139772 KB Output is correct
21 Correct 81 ms 139712 KB Output is correct
22 Correct 82 ms 139720 KB Output is correct
23 Correct 80 ms 139628 KB Output is correct
24 Correct 81 ms 139604 KB Output is correct
25 Correct 81 ms 139592 KB Output is correct
26 Correct 81 ms 139620 KB Output is correct
27 Correct 80 ms 139664 KB Output is correct
28 Correct 83 ms 139600 KB Output is correct
29 Correct 89 ms 139676 KB Output is correct
30 Correct 83 ms 139680 KB Output is correct

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 139544 KB Output is correct
2 Correct 81 ms 139652 KB Output is correct
3 Runtime error 175 ms 262144 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -