제출 #1313603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313603		vlomaczk	Village (BOI20_village)	C++20	6 / 100	1095 ms	33460 KiB

Village

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int M = 100'001;
vector<vector<int>> g(M);
vector<vector<int>> dp(M, vector<int>(2));
vector<int> rep(M), deg(M), p(M), sel(M), p2(M);

int Find(int v) {
	return (rep[v]==v ? v : rep[v]=Find(rep[v]));
}

void Union(int a, int b){
	rep[Find(a)] = Find(b);
}

void dfs(int v, int p) {
	for(auto u : g[v]) if(u!=p) dfs(u,v);
	dp[v][1] = dp[v][0] = 0;
	for(auto u : g[v]) {
		if(u==p) continue;
		dp[v][0] += min(dp[u][0]+1, dp[u][1]);
		dp[v][1] += dp[u][0]+1;
		sel[v] = u;
	}
	for(auto u : g[v]) {
		if(u==p) continue;
		int val = dp[v][0]-min(dp[u][0]+1, dp[u][1]) + dp[u][0] + 1;
		if(val < dp[v][1]) {
			dp[v][1] = val;
			sel[v] = u;
		}
	}
	if(dp[v][1]==0) dp[v][1] = 1e9;
}

void add_edge(int a, int b) {
	deg[a]++; deg[b]++;
	Union(a,b);
}

void odzysk(int v, int p, int t) {
	if(t==1) {
		for(auto u : g[v]) {
			if(u==p) continue;
			if(dp[u][0]+1 < dp[u][1] || u==sel[v]) {
				add_edge(u,v);
				odzysk(u,v,0);
			} else {
				odzysk(u,v,1);
			}
		}
	} else {
		for(auto u : g[v]) {
			if(u==p) continue;
			if(dp[u][0]+1 < dp[u][1]) {
				add_edge(u,v);
				odzysk(u,v,0);
			} else {
				odzysk(u,v,1);
			}
		}
	}
}

vector<int> is_off(M), parent(M), sajz(M), ctr_par(M);
vector<vector<set<pair<int, int>>>> info(M);
vector<set<pair<int, int>>> best_moj(M);
vector<set<pair<int, pair<int, int>>>> gdzie(M);
vector<pair<ll, pair<ll, ll>>> wynik_moj(M);
vector<set<pair<ll, pair<ll, ll>>>> subtree_wynik(M);
vector<vector<int>> gctr(M);

void sajz_dfs(int v, int p) {
	parent[v] = p;
	sajz[v] = 1;
	for(auto u : g[v]) {
		if(u==p || is_off[u]) continue;
		sajz_dfs(u, v);
		sajz[v] += sajz[u];
	}
}

void info_dfs(int v, int p, int ctr, int d) {
	info[ctr].back().insert({d,v});
	gdzie[ctr].insert({v,{info[ctr].size()-1,d}});
	for(auto u : g[v]) {
		if(u==p || is_off[u]) continue;
		info_dfs(u, v, ctr, d+1);
	}
}
 
int find_centroid(int v, int tree_size) {
	for(auto u : g[v]) {
		if(is_off[u]) continue;
		if(u == parent[v]) {
			if(tree_size-sajz[v] > (tree_size+1)/2) return find_centroid(u, tree_size);
		} else {
			if(sajz[u] > (tree_size+1)/2) return find_centroid(u, tree_size);
		}
	}
	return v;
}

pair<ll, pair<ll, ll>> find_best(ll ctr) {
	return wynik_moj[ctr];
}

void merge(int v) {
	wynik_moj[v] = {0,{0,0}};
	if(best_moj[v].size() >= 2) {
		auto[a,b] = *best_moj[v].rbegin();
		auto[c,d] = *next(best_moj[v].rbegin());
		wynik_moj[v] = {a+c, {b,d}};
	}
	if(subtree_wynik[v].size()) wynik_moj[v] = max(wynik_moj[v], *subtree_wynik[v].rbegin());
}

void del(int v) {
	int ctr = ctr_par[v];
	while(ctr) {
		auto[idx,depth] = gdzie[ctr].lower_bound(make_pair(v,make_pair(0,0)))->second;
		if(info[ctr][idx].size()) best_moj[ctr].erase(*info[ctr][idx].rbegin());
		info[ctr][idx].erase({depth,v});
		if(info[ctr][idx].size()) best_moj[ctr].insert(*info[ctr][idx].rbegin());
		subtree_wynik[ctr_par[ctr]].erase(wynik_moj[ctr]);
		merge(ctr);
		subtree_wynik[ctr_par[ctr]].insert(wynik_moj[ctr]);
		ctr = ctr_par[ctr];
	}
}

int centroid_decomposition(int v, int tree_size) {
	sajz_dfs(v, 0);
	int centr = find_centroid(v, tree_size);
	for(auto u : g[centr]) {
		if(is_off[u]) continue;
		info[centr].push_back({});
		info_dfs(u,centr,centr,1);
		if(info[centr].back().size()) best_moj[centr].insert(*info[centr].back().rbegin());
	}
	is_off[centr] = 1;
	for(auto u : g[centr]) {
		if(is_off[u]) continue;
		if(u==parent[centr]) {
			int c = centroid_decomposition(u, tree_size-sajz[centr]);
			gctr[centr].push_back(c);
			ctr_par[c] = centr;
		} else {
			int c = centroid_decomposition(u, sajz[u]);
			gctr[centr].push_back(c);
			ctr_par[c] = centr;
		}
	}
	for(auto u : gctr[centr]) {
		subtree_wynik[centr].insert(wynik_moj[u]);
	}
	merge(centr);
	return centr;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	for(int i=0; i<M; ++i) rep[i] = i;

	int 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);
	}
	ll res = 2;
	ll main_ctr = centroid_decomposition(1,n);
	set<int> V;
	for(int i=1; i<=n; ++i) V.insert(i);
	while(V.size() > 3) {
		auto[d, stat] = find_best(main_ctr);
		res += d;
		auto[a,b] = stat;
		del(a);
		// cout << find_best(main_ctr).first << " " << find_best(main_ctr).second.first << " " << find_best(main_ctr).second.second << "\n";
		// for(auto[xxx,yyy] : best_moj[3]) cout << "(" << xxx << " " << yyy << ") "; cout << "\n";
		del(b);
		// cout << find_best(main_ctr).first << " " << find_best(main_ctr).second.first << " " << find_best(main_ctr).second.second << "\n";
		p2[a] = b;
		p2[b] = a;
		V.erase(a); V.erase(b);
		// cout << d << " - " << a << " " << b << "\n";
	}
	int x1 = *V.begin(); V.erase(x1);
	int x2 = *V.begin(); V.erase(x2);
	if(V.empty()) {
		p2[x1] = x2;
		p2[x2] = x1;
	} else {
		int x3 = *V.begin(); V.erase(x3);
		p2[x1] = x2;
		p2[x2] = x3;
		p2[x3] = x1;
	}

	dfs(1,0);
	odzysk(1,0,1);
	vector<vector<int>> S(n+1);
	for(int i=1; i<=n; ++i) {
		S[rep[i]].push_back(i);
	}
	for(int i=1; i<=n; ++i) {
		if(S[i].empty()) continue;
		int c=0;
		vector<int> vec;
		for(auto x : S[i]) {
			if(deg[x]==1) vec.push_back(x);
			else c=x;
		}
		if(c==0) {
			c=vec.back(); vec.pop_back();
		}
		while(vec.size() > 2) {
			int a = vec.back(); vec.pop_back();
			int b = vec.back(); vec.pop_back();
			p[a] = b;
			p[b] = a;
		}
		int a = vec.back(); vec.pop_back();
		if(vec.empty()) {
			p[a] = c;
			p[c] = a;
			continue;
		}
		int b = vec.back(); vec.pop_back();
		p[a] = b;
		p[b] = c;
		p[c] = a;
	}
	cout << 2*dp[1][1] << " " << 2*res << "\n";
	for(int i=1; i<=n; ++i) cout << p[i] << " "; cout << '\n';
	for(int i=1; i<=n; ++i) cout << p2[i] << " "; cout << '\n';

	return 0;
}

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