oj.uz

Submission #276087

# Submission time Handle Problem Language Result Execution time Memory
276087 2020-08-20T10:40:20 Z shrek12357 Ball Machine (BOI13_ballmachine) C++14
91.4286 / 100
 1000 ms 33904 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;
set<int> balls;

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.insert(cur);
				p.pop();
			}
			cout << cur << endl;
		}
		else {
			int curNode = b;
			for (int j = 19; j >= 0; j--) {
				if (balls.find(anc[curNode][j]) != balls.end()) {
					curNode = anc[curNode][j];
				}
			}
			balls.erase(curNode);
			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 652 ms 17268 KB Output is correct
3 Correct 388 ms 15088 KB Output is correct
4 Correct 4 ms 5760 KB Output is correct
5 Correct 5 ms 5888 KB Output is correct
6 Correct 8 ms 6016 KB Output is correct
7 Correct 9 ms 6016 KB Output is correct
8 Correct 10 ms 6016 KB Output is correct
9 Correct 47 ms 6528 KB Output is correct
10 Correct 128 ms 8824 KB Output is correct
11 Correct 643 ms 17148 KB Output is correct
12 Correct 399 ms 15044 KB Output is correct
13 Correct 516 ms 15100 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 10492 KB Output is correct
2 Correct 987 ms 26352 KB Output is correct
3 Correct 443 ms 19076 KB Output is correct
4 Correct 483 ms 12932 KB Output is correct
5 Correct 551 ms 12408 KB Output is correct
6 Correct 493 ms 11512 KB Output is correct
7 Correct 510 ms 11124 KB Output is correct
8 Correct 275 ms 10360 KB Output is correct
9 Correct 823 ms 26792 KB Output is correct
10 Correct 935 ms 26476 KB Output is correct
11 Correct 772 ms 23816 KB Output is correct
12 Correct 814 ms 23532 KB Output is correct
13 Correct 455 ms 26476 KB Output is correct
14 Correct 417 ms 19184 KB Output is correct

Subtask #3
31.4285714286 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 17692 KB Output is correct
2 Correct 973 ms 26724 KB Output is correct
3 Correct 559 ms 27372 KB Output is correct
4 Correct 523 ms 23408 KB Output is correct
5 Correct 570 ms 22700 KB Output is correct
6 Correct 552 ms 22768 KB Output is correct
7 Correct 549 ms 21596 KB Output is correct
8 Correct 661 ms 27244 KB Output is correct
9 Correct 896 ms 28996 KB Output is correct
10 Execution timed out 1042 ms 28248 KB Time limit exceeded
11 Correct 997 ms 28332 KB Output is correct
12 Execution timed out 1052 ms 26720 KB Time limit exceeded
13 Execution timed out 1062 ms 33904 KB Time limit exceeded
14 Correct 665 ms 23656 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 933 ms 26936 KB Output is correct
2 Correct 982 ms 25212 KB Output is correct
3 Correct 476 ms 29032 KB Output is correct
4 Correct 929 ms 26996 KB Output is correct
5 Correct 979 ms 26144 KB Output is correct
6 Correct 698 ms 23540 KB Output is correct
7 Correct 891 ms 25456 KB Output is correct
8 Correct 461 ms 29032 KB Output is correct
9 Correct 414 ms 19160 KB Output is correct