Submission #445326

#	Time	Username	Problem	Language	Result	Execution time	Memory
445326		grt	Papričice (COCI20_papricice)	C++17	110 / 110	311 ms	28356 KiB

papricice

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 200 * 1000 + 10, INF = 1e9;
int n;
vi V[nax];
multiset<int>lft, overme;
int dp[nax];
int ans;

void dfs2(int x, int p) {
	dp[x] = 1;
	for(int nbh : V[x]) if(nbh != p) {
		dfs2(nbh, x);
		dp[x] += dp[nbh];
	}
}

int f(int a, int b, int c) {
	return max({a,b,c}) - min({a,b,c});
}

void dfs(int x, int p) {
	int best = (n - dp[x]) / 2;
	auto it = lft.lower_bound(best);
	if(it != lft.end()) {
		ans = min(ans, f(dp[x], (*it), n - dp[x] - (*it)));
	}
	if(it != lft.begin()) {
		it = prev(it);
		ans = min(ans, f(dp[x], (*it), n - dp[x] - (*it)));
	}
	best = (n + dp[x]) / 2;
	it = overme.lower_bound(best);
	if(it != overme.end()) {
		ans = min(ans, f(dp[x], (*it) - dp[x], n - (*it)));
	}
	if(it != overme.begin()) {
		it = prev(it);
		ans = min(ans, f(dp[x], (*it) - dp[x], n - (*it)));
	}
	overme.insert(dp[x]);
	for(int nbh : V[x]) if(nbh != p) {
		dfs(nbh, x);
	}
	lft.insert(dp[x]);
	overme.erase(overme.find(dp[x]));
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int a, b, i = 1; i < n; ++i) {
		cin >> a >> b;
		V[a].PB(b);
		V[b].PB(a);
	}
	ans = INF;
	dfs2(1, 0);
	dfs(1, 0);
	cout << ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60