oj.uz

Submission #737143

# Submission time Handle Problem Language Result Execution time Memory
737143 2023-05-06T17:18:42 Z penguin133 Village (BOI20_village) C++17
50 / 100
 258 ms 74572 KB 
#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;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		val = 0, pos = s;
		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;
		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;
		}
	}
	
	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));
	}
	
}*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({sz[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;
		}
	}
	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

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

Subtask #1
6.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5164 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5164 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5164 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Partially correct 3 ms 5204 KB Partially correct
10 Partially correct 3 ms 5204 KB Partially correct
11 Correct 3 ms 5164 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct
13 Partially correct 4 ms 5204 KB Partially correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 3 ms 5160 KB Output is correct
16 Correct 3 ms 5216 KB Output is correct
17 Correct 3 ms 5204 KB Output is correct

Subtask #2
19.0 / 38.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 5332 KB Partially correct
2 Partially correct 3 ms 5332 KB Partially correct
3 Partially correct 5 ms 5332 KB Partially correct
4 Partially correct 4 ms 5588 KB Partially correct
5 Partially correct 4 ms 5588 KB Partially correct
6 Partially correct 4 ms 5588 KB Partially correct
7 Correct 4 ms 5716 KB Output is correct
8 Partially correct 4 ms 5588 KB Partially correct
9 Partially correct 4 ms 5588 KB Partially correct
10 Correct 4 ms 5716 KB Output is correct
11 Partially correct 4 ms 5716 KB Partially correct
12 Correct 4 ms 5680 KB Output is correct
13 Partially correct 4 ms 5588 KB Partially correct
14 Partially correct 4 ms 5588 KB Partially correct
15 Partially correct 4 ms 5588 KB Partially correct
16 Correct 4 ms 5588 KB Output is correct
17 Partially correct 4 ms 5588 KB Partially correct
18 Partially correct 4 ms 5548 KB Partially correct
19 Partially correct 5 ms 5588 KB Partially correct
20 Partially correct 4 ms 5660 KB Partially correct
21 Partially correct 4 ms 5588 KB Partially correct
22 Partially correct 5 ms 5588 KB Partially correct
23 Partially correct 4 ms 5588 KB Partially correct
24 Partially correct 4 ms 5588 KB Partially correct
25 Correct 3 ms 5332 KB Output is correct
26 Partially correct 4 ms 5588 KB Partially correct
27 Correct 3 ms 5332 KB Output is correct
28 Partially correct 4 ms 5552 KB Partially correct
29 Partially correct 5 ms 5548 KB Partially correct
30 Partially correct 6 ms 5556 KB Partially correct

Subtask #3
25.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5164 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5164 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5164 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Partially correct 3 ms 5204 KB Partially correct
10 Partially correct 3 ms 5204 KB Partially correct
11 Correct 3 ms 5164 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct
13 Partially correct 4 ms 5204 KB Partially correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 3 ms 5160 KB Output is correct
16 Correct 3 ms 5216 KB Output is correct
17 Correct 3 ms 5204 KB Output is correct
18 Partially correct 3 ms 5332 KB Partially correct
19 Partially correct 3 ms 5332 KB Partially correct
20 Partially correct 5 ms 5332 KB Partially correct
21 Partially correct 4 ms 5588 KB Partially correct
22 Partially correct 4 ms 5588 KB Partially correct
23 Partially correct 4 ms 5588 KB Partially correct
24 Correct 4 ms 5716 KB Output is correct
25 Partially correct 4 ms 5588 KB Partially correct
26 Partially correct 4 ms 5588 KB Partially correct
27 Correct 4 ms 5716 KB Output is correct
28 Partially correct 4 ms 5716 KB Partially correct
29 Correct 4 ms 5680 KB Output is correct
30 Partially correct 4 ms 5588 KB Partially correct
31 Partially correct 4 ms 5588 KB Partially correct
32 Partially correct 4 ms 5588 KB Partially correct
33 Correct 4 ms 5588 KB Output is correct
34 Partially correct 4 ms 5588 KB Partially correct
35 Partially correct 4 ms 5548 KB Partially correct
36 Partially correct 5 ms 5588 KB Partially correct
37 Partially correct 4 ms 5660 KB Partially correct
38 Partially correct 4 ms 5588 KB Partially correct
39 Partially correct 5 ms 5588 KB Partially correct
40 Partially correct 4 ms 5588 KB Partially correct
41 Partially correct 4 ms 5588 KB Partially correct
42 Correct 3 ms 5332 KB Output is correct
43 Partially correct 4 ms 5588 KB Partially correct
44 Correct 3 ms 5332 KB Output is correct
45 Partially correct 4 ms 5552 KB Partially correct
46 Partially correct 5 ms 5548 KB Partially correct
47 Partially correct 6 ms 5556 KB Partially correct
48 Partially correct 204 ms 42760 KB Partially correct
49 Partially correct 225 ms 46504 KB Partially correct
50 Partially correct 199 ms 46384 KB Partially correct
51 Partially correct 140 ms 37376 KB Partially correct
52 Partially correct 205 ms 45988 KB Partially correct
53 Partially correct 161 ms 41924 KB Partially correct
54 Correct 112 ms 38904 KB Output is correct
55 Correct 258 ms 74572 KB Output is correct
56 Correct 238 ms 59940 KB Output is correct
57 Partially correct 213 ms 55096 KB Partially correct
58 Correct 204 ms 51204 KB Output is correct
59 Partially correct 187 ms 46924 KB Partially correct
60 Correct 203 ms 47588 KB Output is correct
61 Partially correct 195 ms 47240 KB Partially correct
62 Partially correct 171 ms 47400 KB Partially correct
63 Partially correct 157 ms 44844 KB Partially correct
64 Partially correct 192 ms 47460 KB Partially correct
65 Partially correct 187 ms 47640 KB Partially correct
66 Partially correct 163 ms 45028 KB Partially correct
67 Partially correct 129 ms 36540 KB Partially correct
68 Partially correct 149 ms 41288 KB Partially correct
69 Partially correct 189 ms 47728 KB Partially correct
70 Partially correct 159 ms 45148 KB Partially correct
71 Partially correct 130 ms 34820 KB Partially correct
72 Partially correct 155 ms 38860 KB Partially correct
73 Partially correct 210 ms 47828 KB Partially correct
74 Partially correct 156 ms 44148 KB Partially correct
75 Partially correct 252 ms 47648 KB Partially correct
76 Partially correct 190 ms 47088 KB Partially correct
77 Partially correct 207 ms 45388 KB Partially correct
78 Partially correct 110 ms 33344 KB Partially correct
79 Partially correct 146 ms 38008 KB Partially correct
80 Partially correct 196 ms 47728 KB Partially correct
81 Partially correct 213 ms 45500 KB Partially correct
82 Partially correct 172 ms 47052 KB Partially correct