oj.uz

Submission #36495

# Submission time Handle Problem Language Result Execution time Memory
36495 2017-12-10T02:13:53 Z cheater2k Ball Machine (BOI13_ballmachine) C++14
100 / 100
 226 ms 24836 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n, q, root;
vector<int> G[N];
int mn[N];
int tout[N], euler[N], TIME, dep[N], par[N][18];
priority_queue < int, vector<int>, greater<int> > avail;
bool inQueue[N];

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

void dfs(int u) {
	sort(G[u].begin(), G[u].end(), [&](int x, int y) {
		return mn[x] < mn[y];
	});
	for (int v : G[u]) {
		dep[v] = dep[u] + 1;
		par[v][0] = u;
		dfs(v);
	}
	tout[u] = ++TIME;
	euler[TIME] = u;
}

int jump(int x) {
	for (int i = 17; i >= 0; --i) if (!inQueue[par[x][i]]) x = par[x][i];
	return x;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		int p; cin >> p;
		if (p == 0) root = i; else G[p].push_back(i);
	}
	prepare(root);
	par[root][0] = root;
	dfs(root);
	for (int j = 1; j < 18; ++j) {
		for (int i = 1; i <= n; ++i) par[i][j] = par[par[i][j-1]][j-1];
	}
	
	for (int i = 1; i <= n; ++i) avail.push(i), inQueue[i] = true; // all nodes are initially available

	while(q--) {
		int type; cin >> type;
		if (type == 1) {
			int k; cin >> k; // the number of balls to be added
			int lst = 0; // the node contains the last ball
			while(k-- > 0) {
				int t = avail.top(); 
				lst = euler[t];
				inQueue[lst] = false;
				avail.pop();
			}
			printf("%d\n", lst);
		} else {
			int x; cin >> x; // the ball is going to be removed
			int p = jump(x); // jump to the lowest parent which has all nodes filled
			avail.push(tout[p]);
			inQueue[p] = true;
			printf("%d\n", dep[x] - dep[p]);
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13216 KB Output is correct
2 Correct 116 ms 14664 KB Output is correct
3 Correct 83 ms 14664 KB Output is correct
4 Correct 0 ms 13216 KB Output is correct
5 Correct 0 ms 13216 KB Output is correct
6 Correct 0 ms 13216 KB Output is correct
7 Correct 3 ms 13216 KB Output is correct
8 Correct 3 ms 13216 KB Output is correct
9 Correct 9 ms 13216 KB Output is correct
10 Correct 19 ms 13632 KB Output is correct
11 Correct 146 ms 14664 KB Output is correct
12 Correct 99 ms 14664 KB Output is correct
13 Correct 93 ms 14664 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15320 KB Output is correct
2 Correct 193 ms 19748 KB Output is correct
3 Correct 106 ms 15580 KB Output is correct
4 Correct 106 ms 15200 KB Output is correct
5 Correct 96 ms 15072 KB Output is correct
6 Correct 79 ms 15076 KB Output is correct
7 Correct 86 ms 14328 KB Output is correct
8 Correct 36 ms 15312 KB Output is correct
9 Correct 186 ms 20180 KB Output is correct
10 Correct 183 ms 19752 KB Output is correct
11 Correct 183 ms 19756 KB Output is correct
12 Correct 173 ms 17712 KB Output is correct
13 Correct 133 ms 23552 KB Output is correct
14 Correct 93 ms 15580 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 16652 KB Output is correct
2 Correct 216 ms 17808 KB Output is correct
3 Correct 119 ms 22652 KB Output is correct
4 Correct 143 ms 18928 KB Output is correct
5 Correct 156 ms 18584 KB Output is correct
6 Correct 119 ms 18588 KB Output is correct
7 Correct 143 ms 17028 KB Output is correct
8 Correct 153 ms 22648 KB Output is correct
9 Correct 193 ms 20176 KB Output is correct
10 Correct 226 ms 19764 KB Output is correct
11 Correct 223 ms 19764 KB Output is correct
12 Correct 206 ms 17800 KB Output is correct
13 Correct 223 ms 24832 KB Output is correct
14 Correct 143 ms 15584 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 20176 KB Output is correct
2 Correct 199 ms 17800 KB Output is correct
3 Correct 123 ms 24836 KB Output is correct
4 Correct 199 ms 20172 KB Output is correct
5 Correct 199 ms 19760 KB Output is correct
6 Correct 149 ms 19760 KB Output is correct
7 Correct 196 ms 17800 KB Output is correct
8 Correct 146 ms 24836 KB Output is correct
9 Correct 106 ms 15584 KB Output is correct