oj.uz

Submission #484532

# Submission time Handle Problem Language Result Execution time Memory
484532 2021-11-04T06:37:59 Z Nimbostratus Papričice (COCI20_papricice) C++17
110 / 110
 182 ms 22420 KB 
#include "bits/stdc++.h"
#define endl '\n'
#define fi first
#define se second
constexpr int maxn = 2e5+5;
constexpr int inf = 1e9;
constexpr int mod = 1e9+7;
using namespace std;
using lint = long long;
using pii = pair<int,int>;

int n, ans;
vector<int> adj[maxn];
int sub[maxn];
map<int, int> a, b;

void calcsub(int u) {
	sub[u] = 1;
	for(int v : adj[u]) {
		if(sub[v])
			continue;
		calcsub(v);
		sub[u] += sub[v];
	}
}

void calcans(int u) {
	map<int, int>::iterator it;
	int mx, mn;
	it = a.lower_bound((n + sub[u] + 1) / 2);
	if(it != a.end()) {
		int x = it->fi;
		mx = max({sub[u], x - sub[u], n - x});
		mn = min({sub[u], x - sub[u], n - x});
		ans = min(ans, mx - mn);
	}
	if(it != a.begin()) {
		it--;
		int x = it->fi;
		mx = max({sub[u], x - sub[u], n - x});
		mn = min({sub[u], x - sub[u], n - x});
		ans = min(ans, mx - mn);
	}
	it = b.lower_bound((n - sub[u] + 1) / 2);
	if(it != b.end()) {
		int x = it->fi;
		mx = max({sub[u], x, n - sub[u] - x});
		mn = min({sub[u], x, n - sub[u] - x});
		ans = min(ans, mx - mn);
	}
	if(it != b.begin()) {
		it--;
		int x = it->fi;
		mx = max({sub[u], x, n - sub[u] - x});
		mn = min({sub[u], x, n - sub[u] - x});
		ans = min(ans, mx - mn);
	}
}

void dfs(int u) {
	calcans(u);
	a[sub[u]]++;
	for(int v : adj[u]) {
		if(a[sub[v]])
			continue;
		dfs(v);
	}
	a[sub[u]]--;
	if(!a[sub[u]])
		a.erase(sub[u]);
	b[sub[u]]++;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for(int i = 1, x, y; i < n; i++) {
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	ans = inf;
	calcsub(1);
	dfs(1);
	cout << ans << endl;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 2 ms 5012 KB Output is correct
5 Correct 2 ms 4940 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 2 ms 5012 KB Output is correct
5 Correct 2 ms 4940 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5040 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 2 ms 5012 KB Output is correct
5 Correct 2 ms 4940 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5040 KB Output is correct
11 Correct 151 ms 14684 KB Output is correct
12 Correct 173 ms 14660 KB Output is correct
13 Correct 122 ms 15088 KB Output is correct
14 Correct 129 ms 14748 KB Output is correct
15 Correct 180 ms 14612 KB Output is correct
16 Correct 96 ms 14656 KB Output is correct
17 Correct 139 ms 14748 KB Output is correct
18 Correct 182 ms 22420 KB Output is correct
19 Correct 133 ms 14808 KB Output is correct
20 Correct 158 ms 14688 KB Output is correct