Submission #314420

#	Time	Username	Problem	Language	Result	Execution time	Memory
314420		sofapuden	Village (BOI20_village)	C++14	100 / 100	118 ms	20088 KiB

Village

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<vector<ll>> gra;
vector<ll> posmin, posmax, sz, dec1, dec2;

vector<bool> used;

ll ansmin = 0, ansmax = 0, n, cnt = 0;

void dfs(int x, int p){
	sz[x] = 1;
	for(auto i : gra[x]){
		if(i == p)continue;
		dfs(i,x);
		sz[x]+=sz[i];
		if(used[i])continue;
		used[x] = true;
		swap(posmin[x],posmin[i]);
		ansmin += 2;
	}
	if(x)ansmax += min(sz[x], n-sz[x])*2;
	else if(!used[0]){
		swap(posmin[0], posmin[gra[0][0]]);
		ansmin+=2;
	}
}
void findroot(int x, int p){
	for(auto i : gra[x]){
		if(i == p)continue;
		if(sz[i] > n/2){
			dec1[i] = 0;
			dec2[0] = i;
			findroot(i,x);
		}
	}
}
void encode(int x, int p){
	dec1[cnt] = x;
	dec2[x] = cnt++;
	for(auto i : gra[x]){
		if(i == p)continue;
		encode(i,x);
	}
}
	
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	cin >> n;
	gra.resize(n);
	posmin.resize(n);
	posmax.resize(n);
	dec1.resize(n);
	dec2.resize(n);
	sz.resize(n);
	used.resize(n,false);
	iota(posmin.begin(), posmin.end(), 0);
	iota(posmax.begin(), posmax.end(), 0);
	for(int i = 0; i < n-1; ++i){
		int a, b; cin >> a >> b; a--; b--;
		gra[a].push_back(b);
		gra[b].push_back(a);
	}
	dfs(0,0);
	findroot(0,0);
	encode(dec1[0],dec1[0]);
	for(int i = 0; i < n; ++i){
		posmax[i] = dec1[(dec2[i]+n/2)%n];
	}
	cout << ansmin << " " << ansmax << "\n";
	for(auto x : posmin)cout << x+1 << " ";
	cout << "\n";
	for(auto x : posmax)cout << x+1 << " ";
	cout << "\n";
}

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