Submission #737130

#	Time	Username	Problem	Language	Result	Execution time	Memory
737130		penguin133	Village (BOI20_village)	C++17	50 / 100	105 ms	38412 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];

void dfs(int x, int par, int d){
	S[x] = cnt++;
	p[0][x] = par;
	dep[x] = d;
	for(auto i : adj[x]){
		if(i == par)continue;
		dfs(i, x, d + 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;
}
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);
	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++;
		}
	}
	cout << ans * 2 << ' ' << 0 << '\n';
	for(int i=1;i<=n;i++)cout << bru[i] << ' ';
	cout << '\n';
	for(int i=1;i<=n;i++)cout << 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:98:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   98 | main(){
      | ^~~~

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