oj.uz

Submission #466297

# Submission time Handle Problem Language Result Execution time Memory
466297 2021-08-18T13:08:56 Z benson0402 Papričice (COCI20_papricice) C++14
110 / 110
 243 ms 19108 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.upper_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);
		}

	}
	// Case2: Not Ancestor
	{
		auto it = stB.upper_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);
		}

	}
	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 5004 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 5004 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 4 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 5 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 5004 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 4 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 196 ms 12272 KB Output is correct
12 Correct 209 ms 12304 KB Output is correct
13 Correct 184 ms 12756 KB Output is correct
14 Correct 174 ms 12600 KB Output is correct
15 Correct 242 ms 12196 KB Output is correct
16 Correct 144 ms 12884 KB Output is correct
17 Correct 185 ms 12184 KB Output is correct
18 Correct 243 ms 19108 KB Output is correct
19 Correct 198 ms 12320 KB Output is correct
20 Correct 218 ms 12244 KB Output is correct