Submission #1082840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082840		Rawlat_vanak	Village (BOI20_village)	C++17	0 / 100	0 ms	348 KiB

Village

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define ff first
#define ss second
#define pii pair<int,int>
#define pb push_back

vector<vector<int>> graph;
vector<int> sz,order,depth,ansmx,ansmn,first,second;
int n,ctrd,fre,sum;

void dfs(int u,int p){
	order.pb(u);
	for(int v:graph[u]){
		if(v==p) continue;
		if(second[u]==-1 and first[u]!=-1){
			second[u]=v;
		}
		if(first[u]==-1){
			first[u]=v;
		}
		depth[v]=depth[u]+1;
		dfs(v,u);
		sz[u]+=sz[v];
	}
}

int centroid(int u, int p){
	for(int v:graph[u]){
		if(v==p) continue;
		if(sz[v]*2>n){
			return centroid(v,u);
		}
	}
	return u;

}

void mindfs(int u,int p){
	for(int v:graph[u]){
		if(v==p) continue;
		

		mindfs(v,u);
	}
	if(ansmn[u]!=0) return;
	if(graph[p].size()%2==0){
		if(ansmn[p]==0){
			ansmn[p]=u;
			ansmn[u]=p;
			sum+=2;
		}else{
			if(fre==0){
				fre=u;
			}else{
				ansmn[u]=fre;
				ansmn[fre]=u;
				sum+=4;
			}
		}
	}else{
		if(ansmn[p]==0){
			if(u==first[p]){
				ansmn[p]=second[p];
				ansmn[u]=p;
				ansmn[second[p]]=u;
				sum+=4;
			}
		}else{
			if(fre==0){
				fre=u;
			}else{
				ansmn[u]=fre;
				ansmn[fre]=u;
				sum+=4;
			}
		}
	}

}



int32_t main(){
	speedIO;
	int t,m,q;

	//cin>>t;
	t=1;
	while(t--){
		//string s;	
		cin>>n;
		graph.clear();
		graph.resize(n+1);
		sz.clear();
		sz.resize(n+1,1);
		order.clear();
		depth.clear();
		depth.resize(n+1,0);
		ansmx.clear();
		ansmx.resize(n+1);
		ansmn.clear();
		ansmn.resize(n+1,0);
		first.clear();
		first.resize(n+1,-1);
		second.clear();
		second.resize(n+1,-1);


		for(int i=0;i<n-1;i++){
			int u,v;
			cin>>u>>v;
			graph[u].pb(v);
			graph[v].pb(u);

		}
		dfs(1,0);
		ctrd=centroid(1,0);
		depth.clear();
		depth.resize(n+1,0);
		order.clear();
		graph[ctrd].pb(0);
		graph[0].pb(ctrd);
		first.clear();
		first.resize(n+1,-1);
		second.clear();
		second.resize(n+1,-1);
		dfs(ctrd,0);
		int mx=0,mn;
		
		for(int i=1;i<=n;i++){
			mx+=depth[i];
			ansmx[order[i-1]]=order[(i+n/2)%n];
		}
		mx*=2;
		

		mindfs(0,-1);

	

		if(ansmn[ctrd]==0){
			int x=first[ctrd];
			if(ansmn[ansmn[x]]==x){
				ansmn[ctrd]=ansmn[x];
				ansmn[x]=ctrd;
				sum+=2;
			}else{
				ansmn[ansmn[x]]=ctrd;
				ansmn[ctrd]=ansmn[x];
				ansmn[x]=ctrd;
			}
		}

		cout<<mx<<' '<<sum<<'\n';
		for(int i=1;i<=n;i++){
			cout<<ansmx[i]<<' ';
		}
		cout<<'\n';
		for(int i=1;i<=n;i++){
			cout<<ansmn[i]<<' ';
		}
		cout<<'\n';	







		
	}

			
		


		
		

		
		


	//}
	return 0;
}

Compilation message (stderr)

Village.cpp: In function 'int32_t main()':
Village.cpp:132:12: warning: unused variable 'mn' [-Wunused-variable]
  132 |   int mx=0,mn;
      |            ^~
Village.cpp:89:8: warning: unused variable 'm' [-Wunused-variable]
   89 |  int t,m,q;
      |        ^
Village.cpp:89:10: warning: unused variable 'q' [-Wunused-variable]
   89 |  int t,m,q;
      |          ^

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