oj.uz

Submission #871413

# Submission time Handle Problem Language Result Execution time Memory
871413 2023-11-10T19:05:48 Z Onur_Ilgaz Papričice (COCI20_papricice) C++17
110 / 110
 113 ms 25424 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 200005
using namespace std;
vector <vector <int> > adj(N);
set <int> subt;
deque <int> dq;
int under[N];
int n, ans = inf;

void dfs0(int node, int ata) {
	under[node] = 1;
	for(auto it:adj[node]) {
		if(it == ata) continue;
		dfs0(it, node);
		under[node] += under[it];
	}
}

void dfs(int node, int ata) {
	int a = under[node];
	dq.push_front(a);
	// ----------------------------------------
	auto index = subt.lower_bound((n - a) / 2); // >= ilk eleman
	if(index == subt.end() and subt.size()) index--;
	// cout << node << ":\n";
	// for(auto it:dq) {
	// 	cout << it << " ";
	// }
	// cout << "\n";
	if(subt.size()) {
		int b = *(index);
		int c = n - b - a;
		int tans = max(abs(a - b), max(abs(a - c), abs(c - b)));
		ans = min(ans, tans);
		// cout << a << " " << b << " " << c << "\n";
		if(index != subt.end() and index != subt.begin()) {
			index--;
			int b = *(index);
			int c = n - b - a;
			int tans = max(abs(a - b), max(abs(a - c), abs(c - b)));
			ans = min(ans, tans);
			// cout << a << " " << b << " " << c << "\n";
		}
	}
	// ----------------------------------------
	{
		auto ind = lower_bound(dq.begin(), dq.end(), (n + a) / 2);
		if(ind == dq.end()) ind--;
		int b = *(ind) - a;
		int c = n - b - a;
		int tans = max(abs(a - b), max(abs(a - c), abs(c - b)));
		ans = min(ans, tans);
		if(ind != dq.begin()) {
			ind--;
			int b = *(ind) - a;
			int c = n - b - a;
			int tans = max(abs(a - b), max(abs(a - c), abs(c - b)));
			ans = min(ans, tans);
		}
	}
	// ----------------------------------------
	for(auto it:adj[node]) {
		if(it == ata) continue;
		dfs(it, node);
	}
	subt.insert(under[node]);
	dq.pop_front();
}

int32_t main(){
	fast
	cin >> n;
	for(int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs0(1, 0);
	dfs(1, 0);
	cout << ans << "\n";
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 2 ms 4968 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 2 ms 4968 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5260 KB Output is correct
8 Correct 2 ms 5044 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 2 ms 4968 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5260 KB Output is correct
8 Correct 2 ms 5044 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 80 ms 16468 KB Output is correct
12 Correct 90 ms 16624 KB Output is correct
13 Correct 73 ms 16980 KB Output is correct
14 Correct 77 ms 16900 KB Output is correct
15 Correct 113 ms 16464 KB Output is correct
16 Correct 53 ms 16116 KB Output is correct
17 Correct 85 ms 16568 KB Output is correct
18 Correct 111 ms 25424 KB Output is correct
19 Correct 89 ms 16944 KB Output is correct
20 Correct 92 ms 16464 KB Output is correct