Submission #630077

#	Time	Username	Problem	Language	Result	Execution time	Memory
630077		vovamr	Papričice (COCI20_papricice)	C++17	110 / 110	699 ms	31904 KiB

papricice

#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 (stderr)

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 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60