oj.uz

답안 #723224

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723224 2023-04-13T11:18:07 Z gagik_2007 Village (BOI20_village) C++17
0 / 100
 208 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) {
		res_mx[c] = g[c][0];
		res_mx[g[c][0]] = g[c][1];
		res_mx[g[c][1]] = c;
		useds[c] = useds[g[c][0]] = useds[g[c][1]] = true;
	}
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 139592 KB Output is correct
2 Correct 81 ms 139632 KB Output is correct
3 Runtime error 192 ms 262144 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 139604 KB Output is correct
2 Correct 80 ms 139672 KB Output is correct
3 Correct 79 ms 139600 KB Output is correct
4 Correct 86 ms 139596 KB Output is correct
5 Correct 84 ms 139688 KB Output is correct
6 Correct 81 ms 139636 KB Output is correct
7 Correct 83 ms 139724 KB Output is correct
8 Correct 87 ms 139724 KB Output is correct
9 Correct 83 ms 139612 KB Output is correct
10 Correct 80 ms 139720 KB Output is correct
11 Correct 81 ms 139688 KB Output is correct
12 Correct 80 ms 139660 KB Output is correct
13 Runtime error 208 ms 262144 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 139592 KB Output is correct
2 Correct 81 ms 139632 KB Output is correct
3 Runtime error 192 ms 262144 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -