oj.uz

Submission #878015

# Submission time Handle Problem Language Result Execution time Memory
878015 2023-11-24T02:32:20 Z noiaint Papričice (COCI20_papricice) C++17
110 / 110
 133 ms 45276 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25436 KB Output is correct
2 Correct 5 ms 25576 KB Output is correct
3 Correct 6 ms 25436 KB Output is correct
4 Correct 7 ms 25800 KB Output is correct
5 Correct 5 ms 25436 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25436 KB Output is correct
2 Correct 5 ms 25576 KB Output is correct
3 Correct 6 ms 25436 KB Output is correct
4 Correct 7 ms 25800 KB Output is correct
5 Correct 5 ms 25436 KB Output is correct
6 Correct 6 ms 25692 KB Output is correct
7 Correct 6 ms 25692 KB Output is correct
8 Correct 6 ms 25692 KB Output is correct
9 Correct 6 ms 25692 KB Output is correct
10 Correct 8 ms 25692 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25436 KB Output is correct
2 Correct 5 ms 25576 KB Output is correct
3 Correct 6 ms 25436 KB Output is correct
4 Correct 7 ms 25800 KB Output is correct
5 Correct 5 ms 25436 KB Output is correct
6 Correct 6 ms 25692 KB Output is correct
7 Correct 6 ms 25692 KB Output is correct
8 Correct 6 ms 25692 KB Output is correct
9 Correct 6 ms 25692 KB Output is correct
10 Correct 8 ms 25692 KB Output is correct
11 Correct 125 ms 36692 KB Output is correct
12 Correct 119 ms 36772 KB Output is correct
13 Correct 93 ms 37040 KB Output is correct
14 Correct 96 ms 36932 KB Output is correct
15 Correct 125 ms 36564 KB Output is correct
16 Correct 93 ms 36660 KB Output is correct
17 Correct 106 ms 36812 KB Output is correct
18 Correct 133 ms 45276 KB Output is correct
19 Correct 123 ms 36688 KB Output is correct
20 Correct 110 ms 36944 KB Output is correct