oj.uz

Submission #49170

# Submission time Handle Problem Language Result Execution time Memory
49170 2018-05-23T04:29:17 Z aome Ball Machine (BOI13_ballmachine) C++17
100 / 100
 471 ms 21940 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

typedef pair<int, int> ii;

int n, q;
int cnt;
int root;
int p[20][N];
int f[N];
int a[N];
bool in[N];
vector<int> G[N];

void dfs1(int u) {
	f[u] = u;
	for (auto v : G[u]) {
		dfs1(v), f[u] = min(f[u], f[v]);
	}
	sort(G[u].begin(), G[u].end(), [&] (int x, int y) {
		return f[x] < f[y];
	});
}

void dfs2(int u) {
	for (auto v : G[u]) dfs2(v); 
	a[u] = cnt--;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> p[0][i];
		if (!p[0][i]) root = i;
		else {
			G[p[0][i]].push_back(i);
		}
	}
	for (int i = 1; i <= 17; ++i) {
		for (int j = 1; j <= n; ++j) {
			p[i][j] = p[i - 1][p[i - 1][j]];
		}
	}
	cnt = n;
	dfs1(root), dfs2(root);
	priority_queue<ii> pq;
	for (int i = 1; i <= n; ++i) pq.push({a[i], i});
	while (q--) {
		int t, x; cin >> t >> x;
		if (t == 2) {
			int res = 0;
			for (int i = 17; i >= 0; --i) {
				if (in[p[i][x]]) res += (1 << i), x = p[i][x];
			}
			cout << res << '\n';
			in[x] = 0, pq.push({a[x], x});
		}
		else {
			int res = 0;
			while (x--) {
				int tmp = pq.top().second; pq.pop();
				res = tmp, in[tmp] = 1;
			}
			cout << res << '\n';
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2808 KB Output is correct
2 Correct 280 ms 9948 KB Output is correct
3 Correct 227 ms 10020 KB Output is correct
4 Correct 4 ms 10020 KB Output is correct
5 Correct 5 ms 10020 KB Output is correct
6 Correct 6 ms 10020 KB Output is correct
7 Correct 7 ms 10020 KB Output is correct
8 Correct 8 ms 10020 KB Output is correct
9 Correct 20 ms 10020 KB Output is correct
10 Correct 55 ms 10020 KB Output is correct
11 Correct 283 ms 10068 KB Output is correct
12 Correct 261 ms 10392 KB Output is correct
13 Correct 244 ms 10392 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 10392 KB Output is correct
2 Correct 426 ms 17356 KB Output is correct
3 Correct 213 ms 17356 KB Output is correct
4 Correct 191 ms 17356 KB Output is correct
5 Correct 194 ms 17356 KB Output is correct
6 Correct 184 ms 17356 KB Output is correct
7 Correct 330 ms 17356 KB Output is correct
8 Correct 170 ms 17356 KB Output is correct
9 Correct 331 ms 17752 KB Output is correct
10 Correct 320 ms 17752 KB Output is correct
11 Correct 302 ms 17752 KB Output is correct
12 Correct 352 ms 17752 KB Output is correct
13 Correct 246 ms 19564 KB Output is correct
14 Correct 242 ms 19564 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 19564 KB Output is correct
2 Correct 335 ms 19564 KB Output is correct
3 Correct 239 ms 19564 KB Output is correct
4 Correct 237 ms 19564 KB Output is correct
5 Correct 205 ms 19564 KB Output is correct
6 Correct 287 ms 19564 KB Output is correct
7 Correct 272 ms 19564 KB Output is correct
8 Correct 241 ms 19564 KB Output is correct
9 Correct 340 ms 19564 KB Output is correct
10 Correct 373 ms 19564 KB Output is correct
11 Correct 400 ms 19564 KB Output is correct
12 Correct 375 ms 19564 KB Output is correct
13 Correct 390 ms 21940 KB Output is correct
14 Correct 274 ms 21940 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 21940 KB Output is correct
2 Correct 337 ms 21940 KB Output is correct
3 Correct 471 ms 21940 KB Output is correct
4 Correct 372 ms 21940 KB Output is correct
5 Correct 366 ms 21940 KB Output is correct
6 Correct 354 ms 21940 KB Output is correct
7 Correct 395 ms 21940 KB Output is correct
8 Correct 258 ms 21940 KB Output is correct
9 Correct 228 ms 21940 KB Output is correct