Submission #1044085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044085		vjudge1	Village (BOI20_village)	C++17	100 / 100	55 ms	17864 KiB

Village

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define int long long
#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)1e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

int n;
vector<int> adj[MAX];
int mxc[MAX];
int siz[MAX];
int mic[MAX];
int low = 0,high = 0;
vector<int> rt;

void dfs(int u = 1,int p = -1){
	siz[u] = 1;
	rt.push_back(u);
	for(auto v : adj[u]){
		if(v == p)continue;
		dfs(v,u);
		siz[u] += siz[v];
		high += min(n - siz[v],siz[v]);
	}
	
	if(u == mic[u]){
		if(p == -1)swap(mic[u],mic[adj[u][0]]);
		else swap(mic[u],mic[p]);
		low += 2;
	}
}
signed main(){
	
	read();
	
	cin >> n;
	
	for(int i = 1,u,v;i < n;i++){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}	
	
	for(int i = 1;i <= n;i++){
		mic[i] = i;
		mxc[i] = i;
	}
	dfs();
	for(int i = 1;i <= n;i++){
		int u = rt[i - 1];
		int v = rt[(i - 1 + n / 2) % n];
		mxc[u] = v;
	}
	
	cout << low << " " << high * 2 << '\n';
	for(int i = 1;i <= n;i++)cout << mic[i] << " \n"[i == n];
	for(int i = 1;i <= n;i++)cout << mxc[i] << " \n"[i == n];
}

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