oj.uz

Submission #870197

# Submission time Handle Problem Language Result Execution time Memory
870197 2023-11-07T08:33:29 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 663 ms 43336 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, lg = 20;
vector<int> G[N], G2[N];
int n, q, spt[N][lg], h[N], dp[N], s[N], root, a[N];
set<int> S;
map<int, int> mp, mp2;
bool ball[N];

void in() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int p;
		cin >> p;
		a[i] = p;
		if (!p)
			root = i;
		G[i].push_back(p);
		G[p].push_back(i);
	}
}

void dfs(int u = root, int p = 0) {
	spt[u][0] = p;
	dp[u] = u;
	for (int j = 1; j < lg; j++)
		spt[u][j] = spt[spt[u][j - 1]][j - 1];
	for (int v : G[u])
		if (v != p) {
			h[v] = h[u] + 1;
			dfs(v, u);
			dp[u] = min(dp[u], dp[v]);
		}
}

void dfs2(int u = mp2[root], int p = 0) {
	spt[u][0] = p;
	for (int j = 1; j < lg; j++)
		spt[u][j] = spt[spt[u][j - 1]][j - 1];
	for (int v : G2[u])
		if (v != p) {
			h[v] = h[u] + 1;
			dfs2(v, u);
		}
}

int get_par(int u, int x) {
	for (int i = 0; i < lg; i++)
		if ((x >> i) & 1)
			u = spt[u][i];
	return u;
}

int lca(int u, int v) {
	if (h[u] < h[v])
		swap(u, v);
	u = get_par(u, h[u] - h[v]);
	if (u == v)
		return v;
	for (int i = lg - 1; ~i; i--)
		if (spt[v][i] != spt[u][i])
			u = spt[u][i], v = spt[v][i];
	return spt[u][0];
}

bool cmp(const int &a, const int &b) {
	int v = a;
	int u = b;
	int anc = lca(u, v);
	if (anc == v)
		return false;
	if (anc == u)
		return true;	
	v = get_par(v, h[v] - h[anc] - 1);
	u = get_par(u, h[u] - h[anc] - 1);
	return dp[v] < dp[u];
}

void rem(int k) {
	k = mp2[k];
	int u = k;
	for (int i = lg - 1; ~i; i--)
		if (ball[spt[k][i]])
			k = spt[k][i];
	ball[k] = false;
	S.insert(k);
	cout << h[u] - h[k] << endl;
}

void add(int k) {
	int l;
	while(k--) {
		l = *S.begin();
		ball[l] = true;
		S.erase(l);
	}
	cout << mp[l] << endl;
}

void pre() {
	dfs();
	for (int i = 1; i <= n; i++)
		s[i] = i;
	sort(s + 1, s + 1 + n, cmp);
	for (int i = 1; i <= n; i++)
		mp[i] = s[i], mp2[s[i]] = i;
	mp[0] = mp2[0] = 0;
	for (int i = 1; i <= n; i++)
		S.insert(i);
	for (int i = 1; i <= n; i++) {
		a[i] = mp2[a[i]];
		G2[mp2[i]].push_back(a[i]);
		G2[a[i]].push_back(mp2[i]);
		h[i] = 0;
	}
	memset(spt, 0, sizeof spt);
	dfs2();
}

void Q() {
	while(q--) {
		int T, k;
		cin >> T >> k;
		if(T == 1)
			add(k);
		else
			rem(k);
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	in();
	pre();
	Q();
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14428 KB Output is correct
2 Correct 430 ms 28116 KB Output is correct
3 Correct 370 ms 28244 KB Output is correct
4 Correct 3 ms 14428 KB Output is correct
5 Correct 4 ms 14428 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 7 ms 14684 KB Output is correct
8 Correct 7 ms 14684 KB Output is correct
9 Correct 25 ms 15124 KB Output is correct
10 Correct 86 ms 17900 KB Output is correct
11 Correct 427 ms 28100 KB Output is correct
12 Correct 364 ms 28244 KB Output is correct
13 Correct 427 ms 28440 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 20052 KB Output is correct
2 Correct 649 ms 38976 KB Output is correct
3 Correct 529 ms 35368 KB Output is correct
4 Correct 237 ms 21920 KB Output is correct
5 Correct 226 ms 21840 KB Output is correct
6 Correct 232 ms 22296 KB Output is correct
7 Correct 232 ms 21092 KB Output is correct
8 Correct 146 ms 19792 KB Output is correct
9 Correct 561 ms 39132 KB Output is correct
10 Correct 632 ms 39140 KB Output is correct
11 Correct 611 ms 39508 KB Output is correct
12 Correct 643 ms 36524 KB Output is correct
13 Correct 447 ms 40036 KB Output is correct
14 Correct 447 ms 35332 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 26708 KB Output is correct
2 Correct 663 ms 37280 KB Output is correct
3 Correct 344 ms 37312 KB Output is correct
4 Correct 388 ms 34284 KB Output is correct
5 Correct 401 ms 34132 KB Output is correct
6 Correct 429 ms 34220 KB Output is correct
7 Correct 534 ms 32672 KB Output is correct
8 Correct 362 ms 37204 KB Output is correct
9 Correct 577 ms 39344 KB Output is correct
10 Correct 635 ms 39288 KB Output is correct
11 Correct 643 ms 39256 KB Output is correct
12 Correct 595 ms 37244 KB Output is correct
13 Correct 523 ms 43336 KB Output is correct
14 Correct 520 ms 35532 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 39288 KB Output is correct
2 Correct 614 ms 37204 KB Output is correct
3 Correct 432 ms 42980 KB Output is correct
4 Correct 564 ms 39308 KB Output is correct
5 Correct 582 ms 39260 KB Output is correct
6 Correct 583 ms 39148 KB Output is correct
7 Correct 601 ms 37708 KB Output is correct
8 Correct 421 ms 43092 KB Output is correct
9 Correct 462 ms 35460 KB Output is correct