Submission #802136

#	Time	Username	Problem	Language	Result	Execution time	Memory
802136		amirhoseinfar1385	Village (BOI20_village)	C++17	50 / 100	61 ms	18940 KiB

Village

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
vector<int>adj[maxn];
int n,m,sz[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;
}

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);
	cout<<0<<" "<<res<<"\n";
	for(int i=0;i<n;i++){
		cout<<1<<" ";
	}
	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: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50