oj.uz

Submission #276061

# Submission time Handle Problem Language Result Execution time Memory
276061 2020-08-20T10:26:29 Z shrek12357 Ball Machine (BOI13_ballmachine) C++14
16.2271 / 100
 655 ms 73232 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];
map<int, vector<int>> adjList;
int root;
int counter = 0;
int order[MAXN];

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


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]);
		pq[src].push(dp[i]);
	}
}

void dfs2(int src) {
	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);
	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
3.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 7040 KB Execution killed with signal 11
2 Runtime error 215 ms 33528 KB Execution killed with signal 11
3 Correct 443 ms 17088 KB Output is correct
4 Runtime error 9 ms 6944 KB Execution killed with signal 11
5 Runtime error 12 ms 7164 KB Execution killed with signal 11
6 Runtime error 12 ms 7424 KB Execution killed with signal 11
7 Runtime error 14 ms 7424 KB Execution killed with signal 11
8 Runtime error 14 ms 7352 KB Execution killed with signal 11
9 Runtime error 43 ms 8824 KB Execution killed with signal 11
10 Runtime error 97 ms 13688 KB Execution killed with signal 11
11 Runtime error 453 ms 33740 KB Execution killed with signal 11
12 Correct 439 ms 17016 KB Output is correct
13 Runtime error 472 ms 33876 KB Execution killed with signal 11

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 9848 KB Output is correct
2 Runtime error 619 ms 58744 KB Execution killed with signal 11
3 Correct 470 ms 24688 KB Output is correct
4 Runtime error 146 ms 23032 KB Execution killed with signal 11
5 Runtime error 328 ms 22644 KB Execution killed with signal 11
6 Runtime error 312 ms 22776 KB Execution killed with signal 11
7 Runtime error 107 ms 19960 KB Execution killed with signal 11
8 Correct 285 ms 9652 KB Output is correct
9 Runtime error 274 ms 60152 KB Execution killed with signal 11
10 Runtime error 579 ms 58744 KB Execution killed with signal 11
11 Runtime error 570 ms 58872 KB Execution killed with signal 11
12 Runtime error 590 ms 52984 KB Execution killed with signal 11
13 Correct 510 ms 32632 KB Output is correct
14 Correct 469 ms 24688 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 304 ms 33784 KB Execution killed with signal 11
2 Runtime error 596 ms 54136 KB Execution killed with signal 11
3 Runtime error 436 ms 59768 KB Execution killed with signal 11
4 Runtime error 437 ms 49832 KB Execution killed with signal 11
5 Runtime error 391 ms 48376 KB Execution killed with signal 11
6 Runtime error 425 ms 48376 KB Execution killed with signal 11
7 Runtime error 406 ms 44536 KB Execution killed with signal 11
8 Runtime error 403 ms 59768 KB Execution killed with signal 11
9 Runtime error 629 ms 60536 KB Execution killed with signal 11
10 Runtime error 655 ms 58836 KB Execution killed with signal 11
11 Runtime error 613 ms 58844 KB Execution killed with signal 11
12 Runtime error 618 ms 54100 KB Execution killed with signal 11
13 Runtime error 632 ms 73232 KB Execution killed with signal 11
14 Runtime error 236 ms 54664 KB Execution killed with signal 11

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 350 ms 60540 KB Execution killed with signal 11
2 Runtime error 652 ms 54128 KB Execution killed with signal 11
3 Correct 552 ms 36344 KB Output is correct
4 Runtime error 344 ms 60536 KB Execution killed with signal 11
5 Runtime error 653 ms 58744 KB Execution killed with signal 11
6 Runtime error 595 ms 58744 KB Execution killed with signal 11
7 Runtime error 608 ms 54136 KB Execution killed with signal 11
8 Correct 549 ms 36600 KB Output is correct
9 Correct 461 ms 24816 KB Output is correct