Submission #1093132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093132		Jawad_Akbar_JJ	Village (BOI20_village)	C++17	50 / 100	82 ms	20676 KiB

Village

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;
vector<int> nei[N], lst;
int Num[N], Num2[N], ch[N], n;
long long Mx = 0, Mn = 0;

void dfs(int u, int p, int c = 0){
	ch[u] = 1;
	for (int i : nei[u]){
		if (i == p)
			continue;
		dfs(i, u, c);
		ch[u] += ch[i];
		Mx += min(n - ch[i], ch[i]);
	}
	if (c == 0)
		return;
	vector<int> vec = {u};
	for (int i : nei[u]){
		if (i == p)
			continue;
		if (Num2[i] == i or (u == 1 and vec.size() == 1)){
			int k = Num2[i];
			Num2[i] = vec.back();
			vec.push_back(k);
		}
	}
	Num2[u] = vec.back();
	Mn += (vec.size() - 1) * 2;
}

int find_cent(int u, int p){
	for (int i : nei[u])
		if (i != p and ch[i] * 2 > ch[1])
			return find_cent(i, u);
	return u;
}

void get(int u, int p){
	for (int i : nei[u])
		if (i != p)
			get(i, u);
	lst.push_back(u);
}
vector<int> get(int a, int b, int c){
	lst.clear();
	get(a, b);
	return lst;
}

void solve(){
	dfs(1, 1, 1);
	int rt = find_cent(1, 1), ind = 0;
	dfs(rt, rt);

	vector<pair<int,int>> vec;
	for (int i : nei[rt])
		vec.push_back({ch[i], i});
	sort(rbegin(vec), rend(vec));

	vector<int> Vec =get(vec[0].second, rt, 1);
	for (int i=1;i<vec.size();i++){
		vector<int> v = get(vec[i].second, rt, 1);
		for (int j : v)
			Num[j] = Vec[ind++], Vec.push_back(j);
	}

	Vec.push_back(rt);
	Num[rt] = Vec[ind++];
	get(vec[0].second, rt, 1);
	for (int i : lst)
		Num[i] = Vec[ind++];
}

int main(){
	cin>>n;

	for (int i=1, a, b;i<n;i++){
		cin>>a>>b;
		nei[a].push_back(b);
		nei[b].push_back(a);
	}
	if (n == 1){
		cout<<1 / 0;
		return 0;
	}

	solve();

	cout<<Mn<<" "<<Mx<<'\n';
	for (int i=1;i<=n;i++)
		cout<<Num2[i]<<' ';
	cout<<'\n';
	for (int i=1;i<=n;i++)
		cout<<Num[i]<<' ';
	cout<<'\n';
}

Compilation message (stderr)

Village.cpp: In function 'void solve()':
Village.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for (int i=1;i<vec.size();i++){
      |               ~^~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:88:11: warning: division by zero [-Wdiv-by-zero]
   88 |   cout<<1 / 0;
      |         ~~^~~

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50