Submission #737153

#	Time	Username	Problem	Language	Result	Execution time	Memory
737153		penguin133	Village (BOI20_village)	C++17	56 / 100	271 ms	77768 KiB

Village

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int S[200005], cnt = 1, E[200005], p[20][200005];
vector <int> adj[200005];
int n, dep[200005], sz[200005], sz2[200005];
int mp[200006];

void dfs(int x, int par, int d){
	S[x] = cnt++;
	p[0][x] = par;
	dep[x] = d;
	sz[x] = 1, sz2[x] = d;
	for(auto i : adj[x]){
		if(i == par)continue;
		dfs(i, x, d + 1);
		sz[x] += sz[i];
		sz2[x] += sz2[i];
	}
	E[x] = cnt - 1;
}

int lca(int u, int v){
	if(dep[u] > dep[v])swap(u, v);
	int diff = dep[v] - dep[u];
	for(int i=19;i>=0;i--)if(diff >> i & 1)v = p[i][v];
	if(u == v)return u;
	for(int i=19;i>=0;i--){
		if(p[i][u] != p[i][v])u = p[i][u], v = p[i][v];
	}
	return p[0][u];
}
int hv[200005], ans, bru[200005], f = 0;
void grr(int x, int par){
	vector <int> tmp;
	for(auto i : adj[x]){
		if(i == par)continue;
		grr(i, x);
		if(hv[i])tmp.push_back(i);
	}
	bool g = 1;
	if((int)tmp.size() >= 2 && (int)tmp.size()%2 == 0){
		int xx = tmp.back(); tmp.pop_back();
		int y = tmp.back(); tmp.pop_back();
		ans += 2;
		bru[x] = xx;
		bru[xx] = y;
		bru[y] = x;
		f = 1;
		g = 0;
	}
	while((int)tmp.size() >= 2){
		int xx = tmp.back(); tmp.pop_back();
		int y = tmp.back(); tmp.pop_back();
		ans += 2;
		bru[xx] = y, bru[y] = xx;
	}
	if(tmp.empty())hv[x] = g;
	else ans++, bru[x] = tmp[0], bru[tmp[0]] = x;
}

struct node{
	int s, e, m, val, pos, val2;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		val = 0, pos = s;
		val2 = e - s + 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
	}
	
	void upd(int p, int v){
		if(s == e){
			val = v;
			if(v == -1)val2--;
		}
		else{
			if(p <= m)l->upd(p, v);
			else r->upd(p, v);
			val = max(l->val, r->val);
			if(l->val >= r->val)pos = l->pos;
			else pos = r->pos;
			val2 = l->val2 + r->val2;
		}
	}
	
	pi qry(int a, int b){
		if(s == a && e == b)return {val, pos};
		else if(b <= m)return l->qry(a, b);
		else if(a > m)return r->qry(a, b);
		else return max(l->qry(a, m), r->qry(m+1, b));
	}
	
	int qr(int a, int b){
		if(a == s && b == e)return val2;
		else if(b <= m)return l->qr(a, b);
		else if(a > m)return r->qr(a, b);
		else return l->qr(a, m) + r->qr(m+1, b);
	}
	
}*root;

int bru2[200005], ans2,  ded[200005];
void grr2(int xx, int par){
	priority_queue <pi> pq;
	for(auto i : adj[xx]){
		if(i == par)continue;
		if(root->qry(S[i], E[i]).fi > -1)pq.push({root->qr(S[i], E[i]), i});
	}
	while((int)pq.size() > 1){
		pi x = pq.top(); pq.pop();
		pi y = pq.top(); pq.pop();
		pi mx = root->qry(S[x.se], E[x.se]);
		pi mx2 = root->qry(S[y.se], E[y.se]);
		ans2 += mx.fi + mx2.fi - 2 * dep[xx];
		root->upd(mx.se, -1);
		root->upd(mx2.se, -1);
		mx.se = mp[mx.se];
		mx2.se = mp[mx2.se];
		bru2[mx.se] = mx2.se;
		bru2[mx2.se] = mx.se;
		ded[mx.se] = ded[mx2.se] = 1;
		sz[x.se]--;
		sz[y.se]--;
		x.fi--;
		y.fi--;
		if(x.fi)pq.push(x);
		if(y.fi)pq.push(y);
	}
	if(!pq.empty() && !ded[xx]){
		pi x = pq.top(); pq.pop();
		pi mx = root->qry(S[x.se], E[x.se]);
		ans2 += mx.fi - dep[xx];
		root->upd(mx.se, -1);
		mx.se = mp[mx.se];
		sz[x.se]--;
		bru2[xx] = mx.se;
		bru2[mx.se] = xx;
		ded[mx.se] = ded[xx] = 1;
	}
	for(auto i : adj[xx]){
		if(i == par)continue;
		grr2(i, xx);
	}
}

int B[500005];
void solve(){
	cin >> n;
	for(int i=1;i<n;i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, -1, 1);
	for(int i=1;i<=19;i++)for(int j=1;j<=n;j++)p[i][j] = p[i-1][p[i-1][j]];
	grr(1, -1);
	root = new node(1, n);
	for(int i=1;i<=n;i++)mp[S[i]] = i;
	for(int i=1;i<=n;i++)root->upd(S[i], dep[i]);
	if(hv[1]){
		int x = adj[1][0];
		int y = bru[x];
		if(bru[y] == x){
			
			ans++;
			bru[1] = x, bru[x] = y, bru[y] = 1;
		}
		else{
			int z = bru[y];
			bru[z] = y;
			bru[1] = x; bru[x] = 1;
			ans++;
		}
	}
	grr2(1, -1);
	for(int i=1;i<=n;i++){
		if(!bru2[i]){
			int x = (i == n ? i - 1 : i + 1);
			int y = bru2[x];
			bru2[i] = x, bru2[x] = y, bru2[y] = i;
			ans2 += (dep[x] + dep[i] - 2 * dep[lca(x, i)] + dep[i] + dep[y] - 2 * dep[lca(i, y)] - dep[x] - dep[y] + 2 * dep[lca(x, y)]) / 2;
		}
	}
	cout << ans * 2 << ' ' << ans2 * 2 << '\n';
	for(int i=1;i<=n;i++)cout << bru[i] << ' ';
	cout << '\n';
	for(int i=1;i<=n;i++)cout << bru2[i] << ' ';
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

Village.cpp:201:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  201 | main(){
      | ^~~~

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