Submission #1326280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326280		tte0	Village (BOI20_village)	C++20	50 / 100	191 ms	28892 KiB

Village

// Author: Teoman Ata Korkmaz
#include <bits/stdc++.h> 
#define int int64_t
using namespace std;
constexpr int N=2e5+5;
///////////////////////////////////////////////////////////
int n,centroid=-1,v_min[N],v_max[N],sz[N],depth[N],bl[N][19];
vector<int> adj[N];

inline void init_dfs(int node,int p){
	// cerr<<"init_dfs: "<<node<<" "<<p<<endl;
	static int d=0;d++;
	depth[node]=d;
	bl[node][0]=p;
	sz[node]=1;
	bool is_centroid=true;
	for(int i:adj[node]){
		if(i==p)continue;
		init_dfs(i,node);
		sz[node]+=sz[i];
		is_centroid&=sz[i]<n/2;
	}
	is_centroid&=sz[node]>=n/2;
	if(is_centroid)centroid=node;
	d--;
}

inline void init_bl(){
	for(int j=0;j<18;j++){
		for(int i=0;i<n;i++){
			bl[i][j+1]=bl[bl[i][j]][j];
		}
	}
}

inline int dfs_min(int node,int p){
	// cerr<<"dfs_min: "<<node<<" "<<p<<endl;
	int hold=-1;
	for(auto i:adj[node]){
		if(i==p)continue;
		int in=dfs_min(i,node);
		if(in!=-1){
			if(hold==-1){
				hold=in;
			}
			else{
				v_min[in]=hold;
				v_min[hold]=in;
			}
		}
	}
	if(hold==-1)return node;
	else{
		v_min[hold]=node;
		v_min[node]=hold;
		return -1;
	}
}

inline void solve_min(){
	int node=dfs_min(0,-1);
	if(node!=-1){
		assert(node==0);
		int tactical=adj[0][0];
		v_min[v_min[tactical]]=node;
		v_min[node]=tactical;
	}
}

inline void dfs_max(int node,int p,vector<int>& st){
	// cerr<<"dfs_max: "<<node<<" "<<p<<endl;
	st.push_back(node);
	for(int i:adj[node]){
		if(i==p)continue;
		dfs_max(i,node,st);
	}
}

inline void solve_max(){
	// cerr<<"centroid: "<<centroid<<endl;
	assert(centroid!=-1);
	vector<int> bt{centroid};
	for(int i:adj[centroid]){
		dfs_max(i,centroid,bt);
	}

	assert(bt.size()==n);

	for(int i=0;i<n;i++){
		v_max[bt[i]]=bt[(i+(n+1)/2)%n];
	}
}

inline int lca(int a,int b){
	// cerr<<"lca: "<<a<<" "<<b<<endl;
	if(depth[a]<depth[b])swap(a,b);

	int diff=depth[a]-depth[b];
	for(int i=0;i<19;i++){
		if(diff&(1<<i))a=bl[a][i];
	}

	if(a==b)return a;

	for(int i=19;i--;){
		if(bl[a][i]!=bl[b][i]){
			a=bl[a][i];
			b=bl[b][i];
		}
	}

	return bl[a][0];
}

inline int dist(int a,int b){
	return depth[a]+depth[b]-2*depth[lca(a,b)];
}

signed main(void){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		x--,y--;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	init_dfs(0,0);
	init_bl();
	solve_min();
	solve_max();

	int ans_min=0;
	int ans_max=0;
	for(int i=0;i<n;i++){
		ans_min+=dist(i,v_min[i]);
		ans_max+=dist(i,v_max[i]);
	}

	// cerr<<"depth: ";for(int i=0;i<n;i++)cerr<<depth[i]<<" ";cerr<<endl;

	cout<<ans_min<<" "<<ans_max<<endl;
	for(int i=0;i<n;i++)cout<<v_min[i]+1<<" ";cout<<endl;
	for(int i=0;i<n;i++)cout<<v_max[i]+1<<" ";cout<<endl;
}

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