oj.uz

Submission #926841

# Submission time Handle Problem Language Result Execution time Memory
926841 2024-02-13T22:22:11 Z NK_ Papričice (COCI20_papricice) C++17
110 / 110
 176 ms 30288 KB 
// 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 152 ms 24160 KB Output is correct
12 Correct 154 ms 24008 KB Output is correct
13 Correct 138 ms 24392 KB Output is correct
14 Correct 144 ms 24200 KB Output is correct
15 Correct 140 ms 24104 KB Output is correct
16 Correct 95 ms 24008 KB Output is correct
17 Correct 130 ms 24148 KB Output is correct
18 Correct 149 ms 30288 KB Output is correct
19 Correct 176 ms 24188 KB Output is correct
20 Correct 133 ms 24072 KB Output is correct