Submission #1293263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293263		mdobric	Village (BOI20_village)	C++20	100 / 100	55 ms	28152 KiB

Village

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005;
int n;
long long d[maxn], dp[maxn], ans[maxn], ans2[maxn], rez;
vector <int> v[maxn], g[maxn];
int br = 1;
set <pair <int, int> > s;
set <pair <int, int> > ::iterator it;

void dfs (int x, int p){
	d[x] = 1;
	for (int i = 0; i < v[x].size(); i++){
		int y = v[x][i];
		if (y != p){
			dfs(y, x);
			d[x] += d[y];
			if (ans2[y] == y){
				swap(ans2[y], ans2[x]);
				rez += 2;
			}
		}
	}
}

int centroid (int x, int p){
	for (int i = 0; i < v[x].size(); i++){
		int y = v[x][i];
		if (y != p and d[y] * 2 > d[1]) return centroid(y, x);
	}
	return x;
}

void dfs2 (int x, int p, int gr){
	g[gr].push_back(x);
	d[x] = 1;
	dp[x] = 0;
	for (int i = 0; i < v[x].size(); i++){
		int y = v[x][i];
		if (y != p){
			int novig = gr;
			if (gr == 0) novig = br, br++;
			dfs2(y, x, novig);
			dp[x] += dp[y] + d[y];
			d[x] += d[y];
		}
	}
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) ans2[i] = i;
	for (int i = 0; i < n - 1; i++){
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1, 0);
	if (ans2[1] == 1) swap(ans2[1], ans2[v[1][0]]), rez += 2;
	int c = centroid(1, 0);
	dfs2(c, 0, 0);
	cout << rez << " " << dp[c] * 2 << "\n";
	for (int i = 1; i <= n; i++) cout << ans2[i] << " ";
	cout << "\n";
	for (int i = 0; i < br; i++){
		s.insert({g[i].size(), i});
	}
	it = s.end();
	it--;
	while ((it -> first) > 1){
		int in1 = it -> second;
		it--;
		int in2 = it -> second;
		s.erase({g[in1].size(), in1});
		s.erase({g[in2].size(), in2});
		ans[g[in1][g[in1].size()-1]] = g[in2][g[in2].size()-1];
		ans[g[in2][g[in2].size()-1]] = g[in1][g[in1].size()-1];
		g[in1].pop_back();
		g[in2].pop_back();
		s.insert({g[in1].size(), in1});
		s.insert({g[in2].size(), in2});
		it = s.end();
		it--;
	}
	int prvi = -1, prosli;
	for (it = s.begin(); it != s.end(); it++){
		if ((it -> first) > 0 and prvi == -1) prvi = it -> second;
		else if ((it -> first) > 0){
			int tr = it -> second;
			ans[g[tr][0]] = g[prosli][0];
		}
		prosli = it -> second;
	}
	ans[g[prvi][0]] = g[prosli][0];
	for (int i = 1; i <= n; i++) cout << ans[i] << " ";
	cout << "\n";
	
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 38 / 38
• Subtask 3: 50 / 50