Submission #715000

#	Time	Username	Problem	Language	Result	Execution time	Memory
715000		TheConverseEngineer	Papričice (COCI20_papricice)	C++17	Compilation error	0 ms	0 KiB

papricice

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define sqr(x) ((ll)(x))*(x)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


template <int n> struct MergeSortTree {
	vi s[2*n] = {};
	void buildFullTree() {
		for (int i = n-1; i > 0; i--) { 
			s[i].resize(sz(s[i<<1]) + sz(s[i<<1|1]));
			merge(all(s[i<<1]), all(s[i<<1|1]), s[i].begin());
		}
	}
	int get_closer(int a, int b, int k) {
		if (abs(k-a) < abs(k-b)) return a;
		return b;
	}
	int find_close(int node, int k) {
		auto iter = lower_bound(all(s[node]), k);
		if(iter==s[node].end()) return *prev(iter);
		return get_closer(*prev(iter), *iter, k);
	}
	
	int closest(int l, int r, int k) { 
		int output = -9999999;
		for (l += n, r += n; l < r; l /= 2, r /= 2) {
			if (l&1) output = get_closer(output, find_close(l++, k), k);
			if (r&1) output = get_closer(output, find_close(--r, k), k);
		}
		return output;
	}
};

int N;
vi adj[200005];

int tin[200005], tout[200005];
MergeSortTree<200005> tree;

int timer = 0;
int dfs(int u, int p) {
	tin[u] = timer++;
	int subsz = 1;
	for (int v : adj[u]) if (v != p) subsz += dfs(v, u);
	tree.s[200005+tin[u]].emplace_back(subsz);
	tout[u] = timer;
	return subsz;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N; FOR(i, 0, N-1) {
		int x, y; cin >> x >> y; x--; y--;
		adj[x].emplace_back(y);
		adj[y].emplace_back(x);
	}
	dfs(0, -1);
	tree.buildFullTree();
	int mn = 9999999;
	FOR(i, 0, N) {
		int X = tree.s[200005+i][0];
		int optY = (N-X)/2;
		int y = -9999999;
		if (tin[i] > 0) y = tree.closest(0, tin[i], optY);
		if (tout[i] < N) y = tree.get_closer(y, tree.closest(tout[i], N, optY), optY);
		mn = min(mn, max(max(X, y), N-X-y) - min(min(X, y), N-X-y));
	}

	cout << mn;
} 

Compilation message (stderr)

Compilation timeout while compiling papricice