oj.uz

Submission #872225

# Submission time Handle Problem Language Result Execution time Memory
872225 2023-11-12T14:27:22 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
40.2381 / 100
 1000 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int N = 1e5 + 7, SQ = 320;
int n, q, s, t, root, h[N], st[N], sz[N], mn[N], indx[N], it[N];
pii tree[N];
vector<int> ad[N];
set<pii> ver, one[N], sq[SQ];

void input() {
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		p--;
		if (p < 0)
			root = i;
		else
			ad[p].push_back(i);
	}
}

void dfs(int v) {
	mn[v] = v;
	for (int u: ad[v]) {
		dfs(u);
		mn[v] = min(mn[v], mn[u]);
	}
}

bool cmp(int u, int v) {
	return mn[u] < mn[v];
}

void dfs2(int v) {
	st[v] = s++;
	sz[v] = 1;
	for (int u: ad[v]) {
		h[u] = h[v] + 1;
		dfs2(u);
		sz[v] += sz[u];
	}
	indx[v] = t++;	
}

void secondProcess() {
	for (int i = 0; i < n; i++)
		tree[i] = {st[i], i};
	sort(tree, tree + n);
	for (int i = 0; i < n; i++)
		it[tree[i].second] = i;
	for (int i = 0; i < n; i++)
		ver.insert({indx[i], i});
}

void addTo(int v) {
	for (int i = it[v]; i < it[v] + sz[v]; i++) 
		if (i % SQ || i + SQ > it[v] + sz[v])
			one[i].insert({h[v], v});
		else {
			sq[i / SQ].insert({h[v], v});
			i += SQ - 1;
		}
}

void toErase(int v) {
	for (int i = it[v]; i < it[v] + sz[v]; i++)
		if (i % SQ || i + SQ > it[v] + sz[v])
			one[i].erase({h[v], v});
		else {
			sq[i / SQ].erase({h[v], v});
			i += SQ - 1;
		}
}

void add(int x) {	
	while (x--) {
		pii p = *ver.begin();
		addTo(p.second);
		ver.erase(ver.begin());
		if (x == 0)
			cout << p.second + 1 << '\n';
	}
}

void output(int v) {
	int p = 0, hi = INT_MAX, i = it[v];
	if (one[i].size()) {
		p = (*one[i].begin()).second;
		hi = h[(*one[i].begin()).second];
	}
	if (sq[i / SQ].size() && h[(*sq[i / SQ].begin()).second] < hi)
		p = (*sq[i / SQ].begin()).second;
	cout << h[v] - h[p] << '\n';
	ver.insert({indx[p], p});
	toErase(p);
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input();
	dfs(root);
	for (int i = 0; i < n; i++)
		sort(ad[i].begin(), ad[i].end(), cmp);
	dfs2(root);
	secondProcess();
	while (q--) {
		int t, v;
		cin >> t >> v;
		if (t == 1)
			add(v);
		else {
			v--;
			output(v);
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 207 ms 31924 KB Output is correct
3 Correct 52 ms 14416 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 10 ms 9260 KB Output is correct
8 Correct 3 ms 9080 KB Output is correct
9 Correct 10 ms 10396 KB Output is correct
10 Correct 35 ms 14912 KB Output is correct
11 Correct 223 ms 31508 KB Output is correct
12 Correct 51 ms 14416 KB Output is correct
13 Correct 513 ms 16472 KB Output is correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11868 KB Output is correct
2 Runtime error 341 ms 131072 KB Execution killed with signal 9
3 Correct 64 ms 16844 KB Output is correct
4 Runtime error 845 ms 131072 KB Execution killed with signal 9
5 Runtime error 475 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1061 ms 48212 KB Time limit exceeded
7 Runtime error 763 ms 131072 KB Execution killed with signal 9
8 Correct 28 ms 11860 KB Output is correct
9 Runtime error 720 ms 131072 KB Execution killed with signal 9
10 Runtime error 348 ms 131072 KB Execution killed with signal 9
11 Execution timed out 1079 ms 112152 KB Time limit exceeded
12 Runtime error 674 ms 131072 KB Execution killed with signal 9
13 Correct 72 ms 23036 KB Output is correct
14 Correct 69 ms 16776 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 384 ms 131072 KB Execution killed with signal 9
2 Runtime error 340 ms 131072 KB Execution killed with signal 9
3 Runtime error 286 ms 131072 KB Execution killed with signal 9
4 Runtime error 527 ms 131072 KB Execution killed with signal 9
5 Runtime error 348 ms 131072 KB Execution killed with signal 9
6 Runtime error 337 ms 131072 KB Execution killed with signal 9
7 Runtime error 332 ms 131072 KB Execution killed with signal 9
8 Runtime error 297 ms 131072 KB Execution killed with signal 9
9 Runtime error 781 ms 131072 KB Execution killed with signal 9
10 Runtime error 327 ms 131072 KB Execution killed with signal 9
11 Runtime error 326 ms 131072 KB Execution killed with signal 9
12 Runtime error 335 ms 131072 KB Execution killed with signal 9
13 Runtime error 598 ms 131072 KB Execution killed with signal 9
14 Correct 114 ms 19916 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 513 ms 131072 KB Execution killed with signal 9
2 Runtime error 348 ms 131072 KB Execution killed with signal 9
3 Correct 78 ms 24916 KB Output is correct
4 Runtime error 488 ms 131072 KB Execution killed with signal 9
5 Runtime error 330 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1039 ms 34664 KB Time limit exceeded
7 Runtime error 340 ms 131072 KB Execution killed with signal 9
8 Correct 78 ms 24864 KB Output is correct
9 Correct 74 ms 16764 KB Output is correct