oj.uz

Submission #276079

# Submission time Handle Problem Language Result Execution time Memory
276079 2020-08-20T10:35:41 Z shrek12357 Ball Machine (BOI13_ballmachine) C++14
71.5079 / 100
 1000 ms 40944 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];
	}
};

//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 4 ms 3584 KB Output is correct
2 Correct 740 ms 19904 KB Output is correct
3 Correct 495 ms 17988 KB Output is correct
4 Correct 3 ms 3456 KB Output is correct
5 Correct 3 ms 3584 KB Output is correct
6 Correct 7 ms 3712 KB Output is correct
7 Correct 8 ms 3712 KB Output is correct
8 Correct 8 ms 3712 KB Output is correct
9 Correct 41 ms 4480 KB Output is correct
10 Correct 127 ms 7792 KB Output is correct
11 Correct 702 ms 19980 KB Output is correct
12 Correct 464 ms 17904 KB Output is correct
13 Correct 659 ms 17864 KB Output is correct

Subtask #2
21.4285714286 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 9720 KB Output is correct
2 Execution timed out 1086 ms 32376 KB Time limit exceeded
3 Correct 568 ms 24556 KB Output is correct
4 Correct 584 ms 13012 KB Output is correct
5 Correct 573 ms 12792 KB Output is correct
6 Correct 517 ms 11640 KB Output is correct
7 Correct 566 ms 11128 KB Output is correct
8 Correct 288 ms 9728 KB Output is correct
9 Execution timed out 1090 ms 32980 KB Time limit exceeded
10 Execution timed out 1076 ms 32620 KB Time limit exceeded
11 Correct 992 ms 30056 KB Output is correct
12 Execution timed out 1053 ms 29420 KB Time limit exceeded
13 Correct 583 ms 32360 KB Output is correct
14 Correct 515 ms 24556 KB Output is correct

Subtask #3
22.8571428571 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 19528 KB Output is correct
2 Execution timed out 1086 ms 32512 KB Time limit exceeded
3 Correct 729 ms 32428 KB Output is correct
4 Correct 703 ms 27928 KB Output is correct
5 Correct 739 ms 27212 KB Output is correct
6 Correct 697 ms 27536 KB Output is correct
7 Correct 654 ms 25576 KB Output is correct
8 Correct 733 ms 32360 KB Output is correct
9 Execution timed out 1079 ms 35360 KB Time limit exceeded
10 Execution timed out 1067 ms 34616 KB Time limit exceeded
11 Execution timed out 1096 ms 34420 KB Time limit exceeded
12 Execution timed out 1089 ms 32624 KB Time limit exceeded
13 Execution timed out 1075 ms 40944 KB Time limit exceeded
14 Correct 774 ms 29292 KB Output is correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1037 ms 33432 KB Time limit exceeded
2 Execution timed out 1074 ms 31092 KB Time limit exceeded
3 Correct 656 ms 36080 KB Output is correct
4 Execution timed out 1018 ms 33472 KB Time limit exceeded
5 Execution timed out 1065 ms 32368 KB Time limit exceeded
6 Correct 891 ms 29892 KB Output is correct
7 Execution timed out 1095 ms 30964 KB Time limit exceeded
8 Correct 710 ms 36080 KB Output is correct
9 Correct 536 ms 24688 KB Output is correct