Submission #1152237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152237		nguyenphong233	Village (BOI20_village)	C++20	50 / 100	53 ms	16264 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 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 minx,maxx;
int idx[MAX],idy[MAX];
vector<int> topo;
int siz[MAX];

void dfs(int u = 1,int p = -1){
	topo.push_back(u);
	siz[u] = 1;
	for(auto v : adj[u]){
		if(v == p)continue;
		dfs(v,u);
		siz[u] += siz[v];
		maxx += min(n - siz[v],siz[v]);
	}
	if(idx[u] == u){
		if(p == -1)swap(idx[u],idx[adj[u][0]]);
		else swap(idx[u],idx[p]);
		minx += 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++){
		idx[i] = i;
		idy[i] = i;
	}
	
	//topo.push_back(0);
	dfs();
	for(int i = 1;i <= n;i++){
		idy[topo[i - 1]] = topo[(i - 1 + n / 2) % n];
	}
	cout << minx << " " << maxx << '\n';
	for(int i = 1;i <= n;i++)cout << idx[i] << " \n"[i == n];
	for(int i = 1;i <= n;i++)cout << idy[i] << " \n"[i == n];
	
}

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