Submission #878015

#	Time	Username	Problem	Language	Result	Execution time	Memory
878015		noiaint	Papričice (COCI20_papricice)	C++17	110 / 110	133 ms	45276 KiB

papricice

#include<bits/stdc++.h>
// #define long long long
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 520
#endif

const int N = 1e6 + 5;
const int MOD = 1e9 + 7; // 998244353
const int inf = INT_MAX; // LLONG_MAX
const int LOG = 25; // LOG + 1
template<class T> bool minimize(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool maximize(T &a, T b) { return a < b ? (a = b, true) : false; }
template<class T> bool add(T &a, T b) { a += b; while (a > MOD) a -= MOD; return true; }

int n;
vector<int> g[N];
int s[N];

int ans = 0;

void DFS(int u, int p) {
	s[u] = 1;
	for (int v : g[u]) if (v != p) {
		DFS(v, u);
		s[u] += s[v];
	}
}

vector<int> closet(const set<int> &s, int v) {
	vector<int> ans;
	auto it = s.upper_bound(v);
	if (it != s.end()) ans.push_back(*it);
	if (it != s.begin()) {
		--it;
		ans.push_back(*it);
	}
	return ans;
}

int calc(int a, int b, int c) {
	return max({a, b, c}) - min({a, b, c});
}
set<int> A, B;
int DFS_calc(int u, int p) {
	int ans = inf;
	for (auto i : closet(A, (n + s[u]) / 2))
		ans = min(ans, calc(s[u], i - s[u], n - i));
	for (auto i : closet(B, (n - s[u]) / 2))
		ans = min(ans, calc(s[u], i, n - s[u] - i));
	A.insert(s[u]);
	for (int v : g[u]) if (v != p)
		ans = min(ans, DFS_calc(v, u));
	A.erase(s[u]);
	B.insert(s[u]);
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}	

	DFS(1, 0);
	int ans = DFS_calc(1, 0);
	cout << ans;

	return 0;
}
// I'm thinking out loud!

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