Submission #1289035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289035		g4yuhg	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	651 ms	43520 KiB

ballmachine

#include<bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK "+"
#define N 100005
#define LOG 16
using namespace std;

const ll offset = 1e6, inf = 1e18;

bool ghuy4g;

struct Node {
	ll sum, mn;
} st[4 * N], f[4 * N];

ll n, q, in[N], out[N], par[N][LOG + 2], timeDfs, dep[N], tour[N], root, sz[N];
vector<ll> adj[N];

bool is[N];

ll mini[N];

bool cmp(ll u, ll v) {
	return mini[u] < mini[v];
}

void dfs1(ll u, ll parent) {
	mini[u] = u;
	for (auto v : adj[u]) {
		if (v == parent) continue;
		dfs1(v, u);
		mini[u] = min(mini[u], mini[v]);
	}
}

void dfs(ll u, ll parent) {
	in[u] = ++ timeDfs;
	sz[u] = 1;
	tour[timeDfs] = u;
	for (auto v : adj[u]) {
		if (v == parent) continue;
		dep[v] = dep[u] + 1;
		par[v][0] = u;
		dfs(v, u);
		sz[u] += sz[v];
	}
	if (adj[u].size() == 1 && u != root) is[u] = 1;
	out[u] = timeDfs;
}

Node cb(Node A, Node B) {
	Node res;
	res.sum = A.sum + B.sum;
	res.mn = min(A.mn, B.mn);
	return res;
}

void build(ll id, ll l, ll r) {
	if (l == r) {
		st[id] = {1, inf};
		if (is[tour[l]]) {
			st[id] = {1, l};
		}
		f[id] = {-1, -1};
		return;
	}
	ll mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	st[id] = cb(st[id * 2], st[id * 2 + 1]);
	f[id] = {-1, -1};
}

void pre() {
	dfs1(root, root);
	for (int i = 1; i <= n; i ++) {
		sort(adj[i].begin(), adj[i].end(), cmp);
	}
	dfs(root, root);
	for (int j = 1; j <= LOG; j ++) {
		for (int i = 1; i <= n; i ++) {
			ll p = par[i][j - 1];
			par[i][j] = par[p][j - 1];
		}
	}
	build(1, 1, n);
}

ll kth_par(ll u, ll k) {
	for (int j = LOG; j >= 0; j --) {
		if (k >= (1 << j)) {
			k -= (1 << j);
			u = par[u][j];
		}
	}
	return u;
}

void lazy(ll id) {
	if (f[id].sum == -1) return;
	st[id] = f[id];
	if (id * 2 < 4 * N) f[id * 2] = f[id];
	if (id * 2 + 1 < 4 * N) f[id * 2 + 1] = f[id];
	f[id] = {-1, -1};
}

Node get(ll id, ll l, ll r, ll L, ll R) {
	lazy(id);
	if (l > R || r < L) return {0LL, inf};
	if (L <= l && r <= R) return st[id];
	ll mid = (l + r) / 2;
	return cb(get(id * 2, l, mid, L, R), get(id * 2 + 1, mid + 1, r, L, R));
}

void update(ll id, ll l, ll r, ll L, ll R, Node v) {
	lazy(id);
	if (l > R || r < L) return;
	if (L <= l && r <= R) {
		f[id] = v;
		lazy(id);
		return;
	}
	ll mid = (l + r) / 2;
	update(id * 2, l, mid, L, R, v);
	update(id * 2 + 1, mid + 1, r, L, R, v);
	st[id] = cb(st[id * 2], st[id * 2 + 1]);
}

void solve1(ll k) { // add k con vao
	ll node = tour[st[1].mn]; // dinh u, dinh thap nhat
	//cout << "bdnode " << node << endl;
	//return;
	ll kq = 0;
	while (k) {
		node = tour[st[1].mn];
		ll l = 0, r = dep[node], ans = 0, ans_u = node;
		Node res;
		ll l2 = 0;
		while (l <= r) {
			ll mid = (l + r) / 2; // nhay len mid con
			ll u = kth_par(node, mid);
			Node xet = get(1, 1, n, in[u], out[u]);
			//cout << "  mid " << mid << " u " << u << " " << xet.sum << " l r " << l << " " << r << endl;
			//if (l2 >= 3) break;
			if (xet.sum <= k) {
				ans = mid;
				ans_u = u;
				res = xet;
				l = mid + 1;
			}
			else {
				r = mid - 1;
			}
		}
		//cout << " ans_u " << ans_u << " " << res.sum << endl;
		// o node u bi mat het, k -= size
		kq = ans_u;
		k -= res.sum;
		update(1, 1, n, in[ans_u], out[ans_u], {0, inf});
		
		ll p = par[ans_u][0];
		if (p) {
			Node xet = get(1, 1, n, in[p], out[p]);
			if (xet.sum == 1) {
				update(1, 1, n, in[p], in[p], {xet.sum, in[p]}); // thanh la
			}
		}
		if (st[1].mn < inf) {
			node = tour[st[1].mn];
		}
	}
	cout << kq << endl;
}

void solve2(ll x) { // rut bong o x, ban dau dinh hld, nhung co nxet: ko co chuyen o par[x][j] co, ma o par[x][j + 2] cung co
	if (get(1, 1, n, in[x], in[x]).sum == 1) {
		cout << -1 << endl;
		return;
	}
	ll l = 0, r = dep[x], ans = -1, ans_u = -1;
	
	while (l <= r) {
		ll mid = (l + r) / 2;
		ll u = kth_par(x, mid);
		Node xet = get(1, 1, n, in[u], in[u]);
		if (xet.sum == 0) {
			ans = mid;
			ans_u = u;
			l = mid + 1;
		}
		else if (xet.sum == 1) {
			r = mid - 1;
		}
		else {
			cout << "ngu";
			exit(4);
		}
	}
	if (ans_u == -1) {
		cout << "ngu2";
		exit(5);
	}
	update(1, 1, n, in[ans_u], in[ans_u], {1, in[ans_u]}); // o u mat bong
	is[ans_u] = 1; // chac chan bien thanh la
	if (par[ans_u][0]) {
		ll p = par[ans_u][0];
		Node xet = get(1, 1, n, in[p], in[p]);
		if (xet.mn == in[p]) {
			update(1, 1, n, in[p], in[p], {xet.sum, inf}); // vi ko con la la
			is[p] = 0;
		}
	}
	cout << abs(dep[ans_u] - dep[x]) << endl;
}

void solve() {
	for (int id = 1; id <= q; id ++) {
		ll type, x;
		cin >> type >> x;
		if (type == 1) {
			solve1(x);
		}
		else {
			solve2(x);
		}
	}
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> q;
    for (int i = 1; i <= n; i ++) {
    	ll p; cin >> p;
    	if (p == 0) {
    		root = i;
    	}
    	else {
    		adj[i].push_back(p);
    		adj[p].push_back(i);
    		//cout << i << " " << p << endl;
    	}
    }
    pre();
    solve();
    
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5