Submission #1088104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088104		freedommo33	Village (BOI20_village)	C++17	100 / 100	68 ms	20360 KiB

Village

#include <bits/stdc++.h>
typedef long long ll;
constexpr int M = 1e5+7;
using namespace std;
vector<vector<ll>> g(M);
ll paramin[M];
ll paramax[M];
ll par[M];
ll sajz[M];
ll kolor[M];
ll odl[M];
vector<ll> preorder;
vector<ll> kolory[M];
int odl2[20][20];
void bfs(){
	queue<ll> q;
	q.push(1);
	preorder.push_back(1);
	while(!q.empty()){
		ll p = q.front();
		q.pop();
		for(auto i:g[p]) if(par[i] == 0 && par[p]!=i){
			q.push(i);
			par[i] = p;
			preorder.push_back(i);
		}
	}
}
void bfs2(ll v){
	queue<ll> q;
	q.push(v);
	while(!q.empty()){
		ll p = q.front();
		q.pop();
		for(auto i:g[p]) if(i != v && odl[i]==0){
			odl[i] = odl[p] + 1;
			q.push(i);
		}
	}
}
ll centroid = 0;
void dfs(ll v){
	pair<ll, ll> maks = {0, 0};
	for(auto i:g[v]) if(i!=par[v]){
		if(sajz[i] > maks.first) maks = {sajz[i], i};
	}
	if(maks.first > sajz[1]/2) dfs(maks.second);
	else centroid = v;
}
void dfs2(ll v, ll k){
	kolor[v] = k;
	for(auto i:g[v]) if(i!=centroid && kolor[i]==0) dfs2(i, k);
}
bool czy(vector<ll> a, vector<ll> b) { return a.size() > b.size(); }

void bfs3(ll v){
	queue<ll> q;
	q.push(v);
	while(!q.empty()){
		int p = q.front();
		q.pop();
		for(auto i:g[p]) if(odl2[v][i] == 0 && i != v){
			odl2[v][i] = odl2[v][p] + 1;
			q.push(i);
		}
	}
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	ll n;
	cin>>n;
	for(int i=1; i<n; i++){
		int a, b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	bfs();
	reverse(preorder.begin(), preorder.end());
	ll minwynik = 0;
	for(auto i:preorder){
		sajz[i] = 1;
		for(auto j:g[i]) if(j!=par[i]) sajz[i] += sajz[j];
		ll last = 0;
		ll p1 = 0, p2 = 0;
		for(auto j:g[i]) if(j!=par[i] && paramin[j]==0){
			if(last==0) last = j;
			else{	
				p1 = last, p2 = j;
				minwynik += 4;
				//cout<<"P1: "<<last<<" "<<j<<endl;
				paramin[last] = j;
				paramin[j] = last;
				last = 0;
			}	
		}
		if(last!=0){
			minwynik += 2;
			//cout<<"P2: "<<i<<" "<<last<<endl;
			paramin[i] = last;
			paramin[last] = i;
		}
		else if(p1!=0){
			//cout<<"P3: "<<p1<<" "<<p2<<" "<<i<<endl;
			paramin[p1] = i;
			paramin[p2] = p1;
			paramin[i] = p2;
		}
	}
	if(paramin[1] == 0){
		bool czy = 0;
		for(auto i:g[1]){
			if(paramin[paramin[i]] == i){
				int a = i, b = paramin[a];
				//cout<<"P4: "<<a<<" "<<b<<endl;
				paramin[a] = 1;
				paramin[b] = a;
				paramin[1] = b;
				minwynik+=2;
				czy = 1;
				break;
			}
		}
		if(czy == 0){
			int a = g[1][0], b = paramin[a], c = paramin[b];
			//cout<<"P5: "<<a<<" "<<b<<endl;
			paramin[b] = c;
			paramin[c] = b;
			paramin[1] = a;
			paramin[a] = 1;
			minwynik+=2;
		}
	}
	dfs(1);
	ll aktk = 0;
	for(auto i:g[centroid]) dfs2(i, ++aktk);
	for(int i=1; i<=n; i++) if(i!=centroid) kolory[kolor[i]].push_back(i);
	priority_queue<pair<int, int>> q;
	for(int i=1; i<=aktk; i++){
		//cout<<kolory[i].size()<<" "<<i<<endl;
		q.push({kolory[i].size(), i});
	}
	bfs2(centroid);
	//for(int i=1; i<=n; i++) cout<<i<<": "<<odl[i]<<endl;
	ll makswyn = 0;
	while(q.size() > 1){
		pair<ll, ll> a = q.top();
		q.pop();
		pair<ll, ll> b = q.top();
		q.pop();
		ll aa = kolory[a.second].back();
		kolory[a.second].pop_back();
		ll bb = kolory[b.second].back();
		kolory[b.second].pop_back();
		//cout<<"PARUJEMY: "<<aa<<" "<<bb<<endl;
		makswyn += (odl[aa] + odl[bb])*2;
		paramax[aa] = bb;
		paramax[bb] = aa;
		a.first--, b.first--;
		if(a.first) q.push(a);
		if(b.first) q.push(b);
	}
	if(!q.empty()){
		pair<ll, ll> a = q.top();
		q.pop();
		ll aa = kolory[a.second].back();
		kolory[a.second].pop_back();
		//cout<<"PARUJEMY: "<<centroid<<" "<<aa<<endl;
		makswyn += odl[aa]*2;
		paramax[centroid] = aa;
		paramax[aa] = centroid;
	}
	if(paramax[centroid] == 0){
		ll x = 1;
		if(centroid == 1) x = 2;
		ll a = paramax[x];
		paramax[a] = centroid;
		paramax[centroid] = x;
	}
	cout<<minwynik<<" "<<makswyn<<endl;
	for(int i=1; i<=n; i++) cout<<paramin[i]<<" ";
	cout<<endl;
	for(int i=1; i<=n; i++) cout<<paramax[i]<<" ";
	cout<<endl;
	//for(int i=1; i<=n; i++) bfs3(i);
	//ll aktmin = 0;
	//for(int i=1; i<=n; i++) aktmin += odl2[i][paramin[i]];
	//ll aktmaks = 0;
	//for(int i=1; i<=n; i++) aktmaks += odl2[i][paramax[i]];
	//if(aktmin == minwynik && aktmaks == makswyn) cout<<"OK"<<endl;
	return 0;
}

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