Submission #1184723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184723		kl0989e	Village (BOI20_village)	C++20	0 / 100	2 ms	3400 KiB

Village

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

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=1e5+10;

vector<vi> graph(maxn);
vi sze(maxn,1);

void dfs(int cur, int prev=-1) {
	for (auto to:graph[cur]) {
		if (to==prev) {
			continue;
		}
		dfs(to,cur);
		sze[cur]+=sze[to];
	}
}

ll ans1=0;
vi to(maxn,-1);

int dfs2(int cur, int prev=-1) {
	vi childs;
	for (auto to:graph[cur]) {
		if (to==prev) {
			continue;
		}
		if (graph[to].size()==1) {
			childs.pb(to);
		}
		else {
			int t=dfs2(to,cur);
			if (t==1) {
				childs.pb(to);
			}
		}
	}
	for (int i=0; i+1<childs.size(); i+=2) {
		to[childs[i]]=childs[i+1];
		to[childs[i+1]]=childs[i];
		ans1+=4;
	}
	if (childs.size()%2) {
		to[childs.back()]=cur;
		to[cur]=childs.back();
		ans1+=2;
		return 0;
	}
	if (cur==0) {
		int a=graph[0][0];
		int b=to[a];
		if (childs.size()>=2) {
			a=childs[0];
			b=to[a];
		}
		else {
			ans1+=2;
		}
		to[cur]=a;
		to[b]=cur;
	}
	return 1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n;
	cin >> n;
	int a,b;
	for (int i=0; i<n-1; i++) {
		cin >> a >> b;
		graph[--a].pb(--b);
		graph[b].pb(a);
	}
	dfs2(0);
	dfs(0);
	ll ans2=0;
	for (int i=1; i<n; i++) {
		ans2+=2*min(sze[i],n-sze[i]);
	}
	cout << ans1 << ' ' << ans2 << '\n';
	for (int i=0; i<n; i++) {
		cout << to[i]+1 << " \n"[i==n-1];
	}
	for (int i=0; i<n; i++) {
		cout << (i+1)%n+1 << " \n"[i==n-1];
	}
    return 0;
}

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