Submission #802151

#	Time	Username	Problem	Language	Result	Execution time	Memory
802151		amirhoseinfar1385	Village (BOI20_village)	C++17	100 / 100	72 ms	23336 KiB

Village

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
vector<int>adj[maxn];
int n,m,sz[maxn],linkmin[maxn],linkmax[maxn];
vector<vector<int>>allk;
long long res=0;

void dfs(int u,int par=0)
{
	sz[u]=1;
	for(auto x:adj[u]){
		if(x!=par){
			dfs(x,u);
			sz[u]+=sz[x];
		}
	}
}

int findcen(int u,int ted,int par=0){
	//cout<<u<<" "<<ted<<" "<<par<<" "<<sz[u]<<endl;
	for(auto x:adj[u]){
		if(x!=par&&sz[x]*2>=ted){
			return findcen(x,ted,u);
		}
	}
	//cout<<u<<endl;
	return u;
}

int finds(){
	dfs(1);
	//cout<<"salam"<<endl;
	return findcen(1,sz[1]);
}

int solve(int u,int rishe,int par=0){
	if(u!=rishe){
		allk.back().push_back(u);
	}
	int ret=1;
	for(auto x:adj[u]){
		if(x!=par){
			if(u==rishe){
				allk.push_back({});
			}
			int z=solve(x,rishe,u);
			res+=2*z;
			ret+=z;
		}
	}
	return ret;
}

long long res2=0;

int solve2(int u,int par=0){
	vector<int>v;
	v.push_back(u);
	for(auto x:adj[u]){
		if(x!=par){
			if(solve2(x,u)==1){
				v.push_back(x);
			}
		}
	}
	if((int)v.size()==1){
		return 1;
	}
	int sz=(int)v.size();
	res2+=sz*2-2;
	for(int j=0;j<sz;j++){
		linkmin[v[j]]=v[(j+1)%sz];
	}
	return 0;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int r=finds();
	//cout<<"salam"<<endl;
	solve(r,r);
	int f=solve2(1);
	if(f==1){
		int wtf=adj[1][0];
		for(int j=1;j<=n;j++){
			if(linkmin[j]==wtf){
				wtf=j;
				break;
			}
		}
		linkmin[wtf]=1;
		linkmin[1]=adj[1][0];
		res2+=2;
	}
	cout<<res2<<" "<<res<<"\n";
	for(int i=1;i<=n;i++){
		cout<<linkmin[i]<<" ";
	}
	cout<<"\n";
	set<pair<int,int>>st;
	for(int i=0;i<(int)allk.size();i++){
		st.insert(make_pair((int)allk[i].size(),i));
	}
	//cout<<"salam"<<endl;
	while((int)st.size()>1){
		auto x=*st.rbegin();
		st.erase(x);
		auto y=*st.rbegin();
		st.erase(y);
		linkmax[allk[y.second].back()]=allk[x.second].back();
		linkmax[allk[x.second].back()]=allk[y.second].back();
		allk[x.second].pop_back();
		allk[y.second].pop_back();
		x.first--;
		y.first--;
		if(x.first>0){
			st.insert(x);
		}
		if(y.first>0){
			st.insert(y);
		}
	}
	if((int)st.size()>0){
		auto x=*st.rbegin();
		int z=allk[x.second].back();
		linkmax[z]=r;
		linkmax[r]=z;
	}
	else{
		if(r!=1){
			linkmax[r]=1;
			linkmax[linkmax[1]]=r;
		}
		else{
			linkmax[r]=2;
			linkmax[linkmax[2]]=r;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<linkmax[i]<<" ";
	}
	cout<<"\n";
}	

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