oj.uz

Submission #276091

# Submission time Handle Problem Language Result Execution time Memory
276091 2020-08-20T10:42:51 Z shrek12357 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 613 ms 29648 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
using namespace std;

#define MAXN 100005

int depth[MAXN];
int par[MAXN];
int anc[MAXN][20];
int dp[MAXN];
vector<int> adjList[MAXN];
int root;
int counter = 0;
int order[MAXN];

class Compare {
public:
	bool operator()(int a, int b) {
		return dp[a] > dp[b];
	}
};

//map<int, priority_queue<int, vector<int>, Compare>> pq;
priority_queue<int, vector<int>, Compare> pq[MAXN];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> p;
int balls[MAXN];

void dfs(int src) {
	dp[src] = src;
	for (auto i : adjList[src]) {
		depth[i] = depth[src] + 1;
		dfs(i);
		dp[src] = min(dp[src], dp[i]);
	}
}

void dfs2(int src) {
	if (adjList[src].size() == 0) {
		p.push(make_pair(counter, src));
		order[src] = counter;
		counter++;
		return;
	}
	while (pq[src].size() > 0) {
		dfs2(pq[src].top());
		pq[src].pop();
	}
	p.push(make_pair(counter, src));
	order[src] = counter;
	counter++;
}

int main() {
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int temp;
		cin >> temp;
		if (temp == 0) {
			root = i;
			temp = i;
		}
		par[i] = temp;
		anc[i][0] = temp;
		if(temp != i)
			adjList[temp].push_back(i);
	}
	for (int k = 1; k < 20; k++) {
		for (int i = 1; i <= n; i++) {
			anc[i][k] = anc[anc[i][k - 1]][k - 1];
		}
	}
	depth[root] = 0;
	dfs(root);
	for (int i = 1; i <= n; i++) {
		for (auto a : adjList[i]) {
			pq[i].push(a);
		}
	}
	dfs2(root);
	for (int i = 0; i < q; i++) {
		int a, b;
		cin >> a >> b;
		if (a == 1) {
			int cur = 0;
			for (int j = 0; j < b; j++) {
				cur = p.top().second;
				balls[cur] = true;
				p.pop();
			}
			cout << cur << endl;
		}
		else {
			int curNode = b;
			for (int j = 19; j >= 0; j--) {
				if (balls[anc[curNode][j]]) {
					curNode = anc[curNode][j];
				}
			}
			balls[curNode] = false;
			p.push(make_pair(order[curNode], curNode));
			cout << depth[b] - depth[curNode] << endl;
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5888 KB Output is correct
2 Correct 438 ms 15216 KB Output is correct
3 Correct 390 ms 15084 KB Output is correct
4 Correct 4 ms 5760 KB Output is correct
5 Correct 5 ms 5888 KB Output is correct
6 Correct 7 ms 6048 KB Output is correct
7 Correct 8 ms 6016 KB Output is correct
8 Correct 9 ms 6016 KB Output is correct
9 Correct 34 ms 6400 KB Output is correct
10 Correct 105 ms 8184 KB Output is correct
11 Correct 480 ms 15172 KB Output is correct
12 Correct 389 ms 15124 KB Output is correct
13 Correct 460 ms 15092 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 10404 KB Output is correct
2 Correct 549 ms 23656 KB Output is correct
3 Correct 437 ms 19020 KB Output is correct
4 Correct 441 ms 11640 KB Output is correct
5 Correct 346 ms 11384 KB Output is correct
6 Correct 324 ms 11384 KB Output is correct
7 Correct 339 ms 10484 KB Output is correct
8 Correct 297 ms 10336 KB Output is correct
9 Correct 568 ms 24808 KB Output is correct
10 Correct 579 ms 23764 KB Output is correct
11 Correct 519 ms 23764 KB Output is correct
12 Correct 580 ms 21940 KB Output is correct
13 Correct 449 ms 26416 KB Output is correct
14 Correct 434 ms 19040 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 15348 KB Output is correct
2 Correct 586 ms 22380 KB Output is correct
3 Correct 397 ms 24944 KB Output is correct
4 Correct 338 ms 20976 KB Output is correct
5 Correct 360 ms 20464 KB Output is correct
6 Correct 387 ms 20308 KB Output is correct
7 Correct 364 ms 19180 KB Output is correct
8 Correct 365 ms 24816 KB Output is correct
9 Correct 553 ms 24832 KB Output is correct
10 Correct 591 ms 24176 KB Output is correct
11 Correct 601 ms 24172 KB Output is correct
12 Correct 607 ms 22380 KB Output is correct
13 Correct 598 ms 29648 KB Output is correct
14 Correct 523 ms 19584 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 24808 KB Output is correct
2 Correct 555 ms 22384 KB Output is correct
3 Correct 493 ms 29164 KB Output is correct
4 Correct 613 ms 24884 KB Output is correct
5 Correct 580 ms 23932 KB Output is correct
6 Correct 547 ms 23916 KB Output is correct
7 Correct 580 ms 22352 KB Output is correct
8 Correct 501 ms 29036 KB Output is correct
9 Correct 425 ms 19184 KB Output is correct