Submission #1185200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185200		kl0989e	Village (BOI20_village)	C++20	50 / 100	157 ms	51204 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;
int n;

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];
	}
}

vector<vi> dp(maxn,vi(2,1e9));
vi to(maxn,-1);

void dfs2(int cur, int prev=-1) {
	if (graph[cur].size()==1 && cur!=0) {
		dp[cur][1]=0;
		return;
	}
	int cnt=0;
	int diff=1e9;
	for (auto to:graph[cur]) {
		if (to==prev) {
			continue;
		}
		dfs2(to,cur);
		cnt+=min(dp[to][0],dp[to][1]+2);
		if (dp[to][1]+2<=dp[to][0]) {
			diff=0;
		}
		else {
			diff=min(diff,dp[to][1]+2-dp[to][0]);
		}
	}
	dp[cur][1]=cnt;
	dp[cur][0]=cnt+diff;
}

pi dfs3(int ii, int cur, int prev=-1) {
	vector<pi> out={{cur,cur}};
	int t=-1;
	if (ii==0 && dp[cur][0]!=dp[cur][1]) {
		for (auto to:graph[cur]) {
			if (to==prev) {
				continue;
			}
			if (dp[to][1]+2-dp[to][0]==dp[cur][0]-dp[cur][1]) {
				t=to;
				break;
			}
		}
	}
	for (auto to:graph[cur]) {
		if (to==prev) {
			continue;
		}
		if (to==t || dp[to][1]+2<=dp[to][0]) {
			out.pb(dfs3(1,to,cur));
		}
		else {
			dfs3(0,to,cur);
		}
	}
	int prv=out.size()-1;
	for (int i=0; i<out.size(); i++) {
		to[out[i].fi]=out[prv].se;
		prv=i;
	}
	return {out[0].fi,to[out[0].fi]};
}

vi to2(maxn,0);
vector<set<pi>> out(maxn);

void dfs4(int cur, int prev=-1) {
	graph[cur].pb(cur);
	out[cur].insert({cur,cur});
	int bg=cur;
	for (auto to:graph[cur]) {
		if (to==prev || to==cur) {
			continue;
		}
		dfs4(to,cur);
		if (out[to].size()>out[bg].size()) {
			bg=to;
		}
	}
	if (sze[cur]<=n-sze[cur]) {
		swap(out[cur],out[bg]);
		for (auto to:graph[cur]) {
			if (to!=cur && to!=prev) {
				for (auto a:out[to]) {
					out[cur].insert(a);
				}
			}
		}
		return;
	}
	swap(out[cur],out[bg]);
	int cnt=0;
	for (auto to:graph[cur]) {
		if (to!=prev) {
			cnt+=out[to].size();
		}
	}
	int pt1=0;
	int pt2=graph[cur].size()-1;
	while (cnt>n-sze[cur]) {
		while (!out[graph[cur][pt1]].size() || graph[cur][pt1]==prev) {
			pt1++;
		}
		while (!out[graph[cur][pt2]].size() || graph[cur][pt2]==prev) {
			pt2--;
		}
		if (cnt-(n-sze[cur])==3) {
			pi a=*out[graph[cur][pt1]].begin();
			pi b=*out[graph[cur][pt2]].begin();
			out[graph[cur][pt1]].erase(a);
			out[graph[cur][pt2]].erase(b);
			while (!out[graph[cur][pt1]].size() || graph[cur][pt1]==prev) {
				pt1++;
			}
			pi c=*out[graph[cur][pt1]].begin();
			out[graph[cur][pt1]].erase(c);
			to2[a.fi]=b.se;
			to2[b.fi]=c.se;
			to2[c.fi]=a.se;
			cnt-=3;
		}
		else if (cnt-(n-sze[cur])>=2) {
			pi a=*out[graph[cur][pt1]].begin();
			pi b=*out[graph[cur][pt2]].begin();
			out[graph[cur][pt1]].erase(a);
			out[graph[cur][pt2]].erase(b);
			to2[a.fi]=b.se;
			to2[b.fi]=a.se;
			cnt-=2;
		}
		else {
			pi a=*out[graph[cur][pt1]].begin();
			pi b=*out[graph[cur][pt2]].begin();
			out[graph[cur][pt1]].erase(a);
			out[graph[cur][pt2]].erase(b);
			to2[a.fi]=b.se;
			to2[b.fi]=a.se;
			out[graph[cur][pt1]].insert({b.fi,a.se});
			cnt-=1;
		}
	}
	bg=cur;
	for (auto to:graph[cur]) {
		if (to!=prev && out[to].size()>out[bg].size()) {
			bg=to;
		}
	}
	swap(out[cur],out[bg]);
	for (auto to:graph[cur]) {
		if (to!=cur && to!=prev) {
			for (auto a:out[to]) {
				out[cur].insert(a);
			}
		}
	}
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	cin >> n;
	int a,b;
	for (int i=0; i<n-1; i++) {
		cin >> a >> b;
		graph[--a].pb(--b);
		graph[b].pb(a);
	}
	dfs(0);
	dfs2(0);
	dfs3(0,0);
	dfs4(0);
	ll ans2=0;
	for (int i=1; i<n; i++) {
		ans2+=2*min(sze[i],n-sze[i]);
	}
	cout << dp[0][0] << ' ' << 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 << to2[i]+1 << " \n"[i==n-1];
	}
    return 0;
}

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50