oj.uz

Submission #276068

# Submission time Handle Problem Language Result Execution time Memory
276068 2020-08-20T10:29:31 Z shrek12357 Ball Machine (BOI13_ballmachine) C++14
16.2271 / 100
 702 ms 73080 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) {
	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);
	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 240 ms 33784 KB Execution killed with signal 11
3 Correct 427 ms 17016 KB Output is correct
4 Runtime error 13 ms 7040 KB Execution killed with signal 11
5 Runtime error 11 ms 7040 KB Execution killed with signal 11
6 Runtime error 14 ms 7424 KB Execution killed with signal 11
7 Runtime error 15 ms 7424 KB Execution killed with signal 11
8 Runtime error 15 ms 7424 KB Execution killed with signal 11
9 Runtime error 40 ms 8696 KB Execution killed with signal 11
10 Runtime error 100 ms 13692 KB Execution killed with signal 11
11 Runtime error 468 ms 33892 KB Execution killed with signal 11
12 Correct 422 ms 17016 KB Output is correct
13 Runtime error 504 ms 33656 KB Execution killed with signal 11

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 9720 KB Output is correct
2 Runtime error 612 ms 58804 KB Execution killed with signal 11
3 Correct 498 ms 24688 KB Output is correct
4 Runtime error 165 ms 23104 KB Execution killed with signal 11
5 Runtime error 357 ms 22520 KB Execution killed with signal 11
6 Runtime error 350 ms 22648 KB Execution killed with signal 11
7 Runtime error 131 ms 19960 KB Execution killed with signal 11
8 Correct 305 ms 9720 KB Output is correct
9 Runtime error 286 ms 60152 KB Execution killed with signal 11
10 Runtime error 656 ms 58708 KB Execution killed with signal 11
11 Runtime error 625 ms 58876 KB Execution killed with signal 11
12 Runtime error 620 ms 53036 KB Execution killed with signal 11
13 Correct 565 ms 32628 KB Output is correct
14 Correct 527 ms 24612 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 389 ms 33756 KB Execution killed with signal 11
2 Runtime error 702 ms 54012 KB Execution killed with signal 11
3 Runtime error 423 ms 60024 KB Execution killed with signal 11
4 Runtime error 411 ms 49784 KB Execution killed with signal 11
5 Runtime error 465 ms 48636 KB Execution killed with signal 11
6 Runtime error 395 ms 48392 KB Execution killed with signal 11
7 Runtime error 394 ms 44536 KB Execution killed with signal 11
8 Runtime error 428 ms 60024 KB Execution killed with signal 11
9 Runtime error 690 ms 60536 KB Execution killed with signal 11
10 Runtime error 672 ms 58848 KB Execution killed with signal 11
11 Runtime error 625 ms 58760 KB Execution killed with signal 11
12 Runtime error 571 ms 54088 KB Execution killed with signal 11
13 Runtime error 651 ms 73080 KB Execution killed with signal 11
14 Runtime error 244 ms 54624 KB Execution killed with signal 11

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 293 ms 60408 KB Execution killed with signal 11
2 Runtime error 569 ms 53880 KB Execution killed with signal 11
3 Correct 545 ms 36364 KB Output is correct
4 Runtime error 289 ms 60536 KB Execution killed with signal 11
5 Runtime error 565 ms 58744 KB Execution killed with signal 11
6 Runtime error 600 ms 58876 KB Execution killed with signal 11
7 Runtime error 586 ms 54008 KB Execution killed with signal 11
8 Correct 549 ms 36472 KB Output is correct
9 Correct 495 ms 24688 KB Output is correct