Submission #1082945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082945		Rawlat_vanak	Village (BOI20_village)	C++17	100 / 100	57 ms	18376 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;
int n,ctrd,fre,sum;

void dfs(int u,int p){
	order.pb(u);
	for(int v:graph[u]){
		if(v==p) continue;
		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;

}

bool mindfs(int u,int p){// in subgraph of u is u used or no
	bool posu=false;
	int curr=-1;
	for(int v:graph[u]){
		if(v==p) continue;
		bool flag=mindfs(v,u);
		if(flag){

		}else{
			posu=true;
			if(curr==-1){
				ansmn[v]=u;
				sum+=1;
				curr=v;
			}else{
				ansmn[v]=curr;
				sum+=2;
				curr=v;
			}
		}
	}
	if(posu){
		ansmn[u]=curr;
		sum+=1;
		return true;
	}else{
		return false;
	}
}



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);

		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();

		dfs(ctrd,0);
		int mx=0;
		
		for(int i=1;i<=n;i++){
			mx+=depth[i];
			ansmx[order[i-1]]=order[(i-1+n+(n/2))%n];
		}
		mx*=2;
		
		sum=0;
		mindfs(ctrd,0);
		
		if(ansmn[ctrd]==0){
			int x=graph[ctrd][0];
			ansmn[ctrd]=ansmn[x];
			ansmn[x]=ctrd;
			sum+=2;
		}
		

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







		
	}

			
		


		
		

		
		


	//}
	return 0;
}

Compilation message (stderr)

Village.cpp: In function 'int32_t main()':
Village.cpp:70:8: warning: unused variable 'm' [-Wunused-variable]
   70 |  int t,m,q;
      |        ^
Village.cpp:70:10: warning: unused variable 'q' [-Wunused-variable]
   70 |  int t,m,q;
      |          ^

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