Submission #484532

#	Time	Username	Problem	Language	Result	Execution time	Memory
484532		Nimbostratus	Papričice (COCI20_papricice)	C++17	110 / 110	182 ms	22420 KiB

papricice

#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 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60