oj.uz

Submission #630077

# Submission time Handle Problem Language Result Execution time Memory
630077 2022-08-15T15:56:59 Z vovamr Papričice (COCI20_papricice) C++17
110 / 110
 699 ms 31904 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 2e5 + 10;

ve<int> gr[N];
set<int> *s[N];
int sz[N], nxt[N];

inline void dfs(int v, int p) {
	sz[v] = 1; nxt[v] = -1;
	for (auto &to : gr[v]) {
		if (to == p) continue;
		dfs(to, v);
		sz[v] += sz[to];
		if (!~nxt[v] || sz[nxt[v]] < sz[to]) nxt[v] = to;
	}
}

int n;
int res;

ve<int>* sub[N];

int fenw[N];
inline void upd(int i, int x) { for (i += 3; i < N; i += i & -i) fenw[i] += x; }
inline int get(int i) { int ans = 0; for (i += 3; i; i -= i & -i){ans += fenw[i];} return ans; }
inline int get(int l, int r) { return get(r) - get(l - 1); }

inline void dfs1(int v, int p, bool keep = 0) {
	for (auto &to : gr[v]) {
		if (to == p || to == nxt[v]) continue;
		dfs1(to, v, 0);
	}
	if (~nxt[v]) dfs1(nxt[v], v, 1);

	if (!~nxt[v]) sub[v] = new ve<int>;
	else sub[v] = sub[nxt[v]];

	for (auto &to : gr[v]) {
		if (to == p || to == nxt[v]) continue;

		for (auto &u : *sub[to]) {
			// sz[w] in [sz[u] - x, sz[u] + x]
			// sz[w] in [n - 2 * sz[u] - x, n - 2 * s[u] + x]
			// sz[w] in 1/2 * [n - sz[u] - x, n  - sz[u] + x]

			const int &S = sz[u];

			int l = 0, r = res - 1, m, ans = res;
			while (l <= r) {
				m = l + r >> 1;
				int L = max({0, S - m, n - 2 * S - m, (n - S - m + 1) / 2});
				int R = min({n, S + m, n - 2 * S + m, (n - S + m) / 2});
				if (L > R) l = m + 1;
				else {
					if (get(L, R)) ans = m, r = m - 1;
					else l = m + 1;
				}
			}
			chmin(res, ans);
		}
		for (auto &u : *sub[to]) {
			(*sub[v]).pb(u);
			upd(sz[u], +1);
		}
	}

	upd(sz[v], +1);
	(*sub[v]).pb(v);

	if (!keep) {
		for (auto &u : *sub[v]) {
			upd(sz[u], -1);
		}
	}
}

inline void dfs2(int v, int p) {

	const int S = sz[v];
	int l = 0, r = res - 1, m, ans = res;

	while (l <= r) {
		m = l + r >> 1;
		int L = max({0, 2 * S - m, n - S - m, (n + S - m + 1) / 2});
		int R = min({n, 2 * S + m, n - S + m, (n + S + m) / 2});
		if (L > R) l = m + 1;
		else {
			if (get(L, R)) ans = m, r = m - 1;
			else l = m + 1;
		}
	}
	chmin(res, ans);

	upd(S, +1);
	for (auto &to : gr[v]) {
		if (to == p) continue;
		dfs2(to, v);
	}
	upd(S, -1);
}

inline void solve() {
	cin >> n; res = n - 2;
	for (int i = 1; i < n; ++i) {
		int v, u;
		cin >> v >> u, --v, --u;
		gr[v].pb(u), gr[u].pb(v);
	}

	dfs(0, 0);
	dfs1(0, 0), dfs2(0, 0);

	cout << res;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message

papricice.cpp: In function 'void dfs1(int, int, bool)':
papricice.cpp:71:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     m = l + r >> 1;
      |         ~~^~~
papricice.cpp: In function 'void dfs2(int, int)':
papricice.cpp:104:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |   m = l + r >> 1;
      |       ~~^~~

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5036 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 5 ms 5204 KB Output is correct
7 Correct 6 ms 5204 KB Output is correct
8 Correct 5 ms 5332 KB Output is correct
9 Correct 5 ms 5204 KB Output is correct
10 Correct 5 ms 5168 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5036 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 5 ms 5204 KB Output is correct
7 Correct 6 ms 5204 KB Output is correct
8 Correct 5 ms 5332 KB Output is correct
9 Correct 5 ms 5204 KB Output is correct
10 Correct 5 ms 5168 KB Output is correct
11 Correct 590 ms 28128 KB Output is correct
12 Correct 647 ms 27148 KB Output is correct
13 Correct 575 ms 31904 KB Output is correct
14 Correct 569 ms 30020 KB Output is correct
15 Correct 669 ms 27812 KB Output is correct
16 Correct 333 ms 31300 KB Output is correct
17 Correct 524 ms 27832 KB Output is correct
18 Correct 261 ms 30276 KB Output is correct
19 Correct 699 ms 30916 KB Output is correct
20 Correct 572 ms 27024 KB Output is correct