oj.uz

Submission #466296

# Submission time Handle Problem Language Result Execution time Memory
466296 2021-08-18T13:04:35 Z benson0402 Papričice (COCI20_papricice) C++14
110 / 110
 241 ms 22468 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define F first
#define S second
#define eb emplace_back
#define ep emplace
#define mkp make_pair
#define ALL(x) x.begin(), x.end()
#define MEM(x) memset(x, 0, sizeof(x));
#define MEMS(x) memset(x, -1, sizeof(x));

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/*-------------------------------------------------------------------------*/

const ll MOD = 1e9 + 7;

const int N = 2e5 + 5;
int n;
vector<int> G[N];
set<int> stA, stB;
int sz[N];

void dfs(int u, int p = -1) {
	sz[u] = 1;
	for(auto& v : G[u]) if(v != p) {
		dfs(v, u);
		sz[u] += sz[v];
	}
}
int ans = INF;
void dfs2(int u, int p = -1) {
	// Case1: is Ancestor
	{
		auto it = stA.lower_bound((n + sz[u]) / 2);
		if(it != stA.end()) {
			// if(u == 7) cout << *it << '\n';
			int mx = max({*it - sz[u], sz[u], n - *it});
			int mn = min({*it - sz[u], sz[u], n - *it});
			ans = min(ans, mx - mn);
		}
		if(it != stA.begin()) {
			auto iit = prev(it);
			// if(u == 7) cout << *it << '\n';
			int mx = max({*iit - sz[u], sz[u], n - *iit});
			int mn = min({*iit - sz[u], sz[u], n - *iit});
			ans = min(ans, mx - mn);
		}
		if(it != stA.end() && it != prev(stA.end())) {
			auto iit = next(it);
			int mx = max({*iit - sz[u], sz[u], n - *iit});
			int mn = min({*iit - sz[u], sz[u], n - *iit});
			ans = min(ans, mx - mn);
		}
	}
	// Case2: Not Ancestor
	{
		auto it = stB.lower_bound((n - sz[u]) / 2);
		if(it != stB.end()) {
			int mx = max({*it, sz[u], n - *it - sz[u]});
			int mn = min({*it, sz[u], n - *it - sz[u]});
			ans = min(ans, mx - mn);
		}
		if(it != stB.begin()) {
			auto iit = prev(it);
			int mx = max({*iit, sz[u], n - *iit - sz[u]});
			int mn = min({*iit, sz[u], n - *iit - sz[u]});
			ans = min(ans, mx - mn);
		}
		if(it != stB.end() && it != prev(stB.end())) {
			auto iit = next(it);
			int mx = max({*iit, sz[u], n - *iit - sz[u]});
			int mn = min({*iit, sz[u], n - *iit - sz[u]});
			ans = min(ans, mx - mn);
		}
	}
	stA.ep(sz[u]);
	for(auto& v : G[u]) if(v != p) {
		dfs2(v, u);
	}
	stA.erase(sz[u]);
	stB.ep(sz[u]);
}


inline void solve() {
	cin >> n;
	for(int i = 0; i < n - 1; ++i) {
		int u, v; cin >> u >> v;
		G[u].eb(v);
		G[v].eb(u);
	}
	dfs(1);
	dfs2(1);
	cout << ans << '\n';
}

signed main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);
    solve();
}

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 3 ms 4940 KB Output is correct
5 Correct 3 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 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 6 ms 5056 KB Output is correct
10 Correct 4 ms 5068 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 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 6 ms 5056 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 216 ms 14660 KB Output is correct
12 Correct 225 ms 14720 KB Output is correct
13 Correct 175 ms 15096 KB Output is correct
14 Correct 178 ms 14796 KB Output is correct
15 Correct 241 ms 14612 KB Output is correct
16 Correct 153 ms 14736 KB Output is correct
17 Correct 194 ms 14660 KB Output is correct
18 Correct 221 ms 22468 KB Output is correct
19 Correct 187 ms 14916 KB Output is correct
20 Correct 202 ms 14836 KB Output is correct