oj.uz

Submission #445326

# Submission time Handle Problem Language Result Execution time Memory
445326 2021-07-17T13:43:54 Z grt Papričice (COCI20_papricice) C++17
110 / 110
 311 ms 28356 KB 
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 200 * 1000 + 10, INF = 1e9;
int n;
vi V[nax];
multiset<int>lft, overme;
int dp[nax];
int ans;

void dfs2(int x, int p) {
	dp[x] = 1;
	for(int nbh : V[x]) if(nbh != p) {
		dfs2(nbh, x);
		dp[x] += dp[nbh];
	}
}

int f(int a, int b, int c) {
	return max({a,b,c}) - min({a,b,c});
}

void dfs(int x, int p) {
	int best = (n - dp[x]) / 2;
	auto it = lft.lower_bound(best);
	if(it != lft.end()) {
		ans = min(ans, f(dp[x], (*it), n - dp[x] - (*it)));
	}
	if(it != lft.begin()) {
		it = prev(it);
		ans = min(ans, f(dp[x], (*it), n - dp[x] - (*it)));
	}
	best = (n + dp[x]) / 2;
	it = overme.lower_bound(best);
	if(it != overme.end()) {
		ans = min(ans, f(dp[x], (*it) - dp[x], n - (*it)));
	}
	if(it != overme.begin()) {
		it = prev(it);
		ans = min(ans, f(dp[x], (*it) - dp[x], n - (*it)));
	}
	overme.insert(dp[x]);
	for(int nbh : V[x]) if(nbh != p) {
		dfs(nbh, x);
	}
	lft.insert(dp[x]);
	overme.erase(overme.find(dp[x]));
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int a, b, i = 1; i < n; ++i) {
		cin >> a >> b;
		V[a].PB(b);
		V[b].PB(a);
	}
	ans = INF;
	dfs2(1, 0);
	dfs(1, 0);
	cout << ans;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 5 ms 5196 KB Output is correct
7 Correct 6 ms 5196 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 5 ms 5156 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 5 ms 5196 KB Output is correct
7 Correct 6 ms 5196 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 5 ms 5156 KB Output is correct
11 Correct 275 ms 23984 KB Output is correct
12 Correct 311 ms 23968 KB Output is correct
13 Correct 229 ms 24356 KB Output is correct
14 Correct 254 ms 24260 KB Output is correct
15 Correct 304 ms 23916 KB Output is correct
16 Correct 197 ms 23872 KB Output is correct
17 Correct 266 ms 24380 KB Output is correct
18 Correct 272 ms 28356 KB Output is correct
19 Correct 247 ms 24092 KB Output is correct
20 Correct 282 ms 24008 KB Output is correct