제출 #926841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
926841		NK_	Papričice (COCI20_papricice)	C++17	110 / 110	176 ms	30288 KiB

papricice

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;

const int INF = 1e9 + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	V<vi> adj(N); for(int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	vi sub(N); 
	function<void(int, int)> gen = [&](int u, int p) {
		sub[u] = 1;
		for(auto& v : adj[u]) if (v != p) {
			gen(v, u); sub[u] += sub[v];
		}	
	};
	
	gen(0, -1);

	int ans = INF; multiset<int> P, R; // parents and rest	
	function<void(int, int)> dfs = [&](int u, int p) {

		if (sz(P)) { // PARENT -> S_u, S_v - S_u, N - S_v
			int opt = (sub[u] + N) / 2;
			// cout << u << " == PAR => " << opt << endl;

			auto it = P.upper_bound(opt);
			if (it != end(P)) {
				int sv = *it;
				// cout << sv << endl;
				ans = min(ans, max({sub[u], sv - sub[u], N - sv}) - min({sub[u], sv - sub[u], N - sv}));
			}

			if (it != begin(P)) {
				int sv = *prev(it);
				// cout << sv << endl;
				ans = min(ans, max({sub[u], sv - sub[u], N - sv}) - min({sub[u], sv - sub[u], N - sv}));
			}

			// cout << u << " == PAR => " << opt << endl;
		}	

		if (sz(R)) { // REST -> S_u, S_v, N - S_v - S_u
			int opt = (N - sub[u]) / 2;
			// cout << u << " == REST => " << opt << endl;

			auto it = R.upper_bound(opt);
			if (it != end(R)) {
				int sv = *it;
				// cout << sv << endl;
				ans = min(ans, max({sub[u], sv, N - sub[u] - sv}) - min({sub[u], sv, N - sub[u] - sv}));
			}

			if (it != begin(R)) {
				int sv = *prev(it);
				// cout << sv << endl;
				ans = min(ans, max({sub[u], sv, N - sub[u] - sv}) - min({sub[u], sv, N - sub[u] - sv}));
			}

			// cout << u << " == REST => " << opt << endl;
		}

		P.insert(sub[u]);
		for(auto& v : adj[u]) if (v != p) {
			dfs(v, u);
		}
		P.erase(P.find(sub[u]));
		R.insert(sub[u]);

	}; 

	dfs(0, -1);

	cout << ans << nl;

	exit(0-0);
}

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