oj.uz

Submission #276053

# Submission time Handle Problem Language Result Execution time Memory
276053 2020-08-20T10:20:05 Z shrek12357 Ball Machine (BOI13_ballmachine) C++14
28.3578 / 100
 1000 ms 47568 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;
map<int, int> order;
int counter = 0;

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

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

map<int, priority_queue<int, vector<int>, Compare>> pq;
priority_queue<int, vector<int>, Compare1> 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) {
	while (pq[src].size() > 0) {
		dfs2(pq[src].top());
		pq[src].pop();
	}
	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 = 1; i <= n; i++) {
		p.push(i);
	}
	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();
				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(curNode);
			cout << depth[b] - depth[curNode] << endl;
		}
	}
}

Subtask #1
19.2307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Execution timed out 1093 ms 24260 KB Time limit exceeded
3 Correct 739 ms 23412 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 7 ms 744 KB Output is correct
7 Correct 11 ms 768 KB Output is correct
8 Correct 12 ms 896 KB Output is correct
9 Correct 71 ms 1912 KB Output is correct
10 Correct 335 ms 6648 KB Output is correct
11 Execution timed out 1100 ms 24692 KB Time limit exceeded
12 Correct 720 ms 23412 KB Output is correct
13 Execution timed out 1092 ms 23780 KB Time limit exceeded

Subtask #2
8.57142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 9332 KB Output is correct
2 Execution timed out 1094 ms 40432 KB Time limit exceeded
3 Correct 802 ms 34160 KB Output is correct
4 Execution timed out 1072 ms 14236 KB Time limit exceeded
5 Execution timed out 1093 ms 13944 KB Time limit exceeded
6 Execution timed out 1093 ms 12908 KB Time limit exceeded
7 Execution timed out 1056 ms 12152 KB Time limit exceeded
8 Correct 394 ms 9368 KB Output is correct
9 Execution timed out 1049 ms 41516 KB Time limit exceeded
10 Execution timed out 1093 ms 39816 KB Time limit exceeded
11 Execution timed out 1048 ms 39544 KB Time limit exceeded
12 Execution timed out 1091 ms 37412 KB Time limit exceeded
13 Execution timed out 1031 ms 40692 KB Time limit exceeded
14 Correct 926 ms 34144 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 22900 KB Time limit exceeded
2 Execution timed out 1046 ms 38908 KB Time limit exceeded
3 Execution timed out 1094 ms 39096 KB Time limit exceeded
4 Execution timed out 1097 ms 34692 KB Time limit exceeded
5 Execution timed out 1089 ms 34040 KB Time limit exceeded
6 Execution timed out 1093 ms 34036 KB Time limit exceeded
7 Execution timed out 1090 ms 32412 KB Time limit exceeded
8 Execution timed out 1095 ms 39024 KB Time limit exceeded
9 Execution timed out 1101 ms 42200 KB Time limit exceeded
10 Execution timed out 1096 ms 40948 KB Time limit exceeded
11 Execution timed out 1068 ms 41108 KB Time limit exceeded
12 Execution timed out 1090 ms 39256 KB Time limit exceeded
13 Execution timed out 1063 ms 47568 KB Time limit exceeded
14 Execution timed out 1089 ms 37580 KB Time limit exceeded

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 41240 KB Time limit exceeded
2 Execution timed out 1082 ms 39080 KB Time limit exceeded
3 Execution timed out 1099 ms 45808 KB Time limit exceeded
4 Execution timed out 1090 ms 42028 KB Time limit exceeded
5 Execution timed out 1100 ms 40564 KB Time limit exceeded
6 Execution timed out 1094 ms 39412 KB Time limit exceeded
7 Execution timed out 1032 ms 38988 KB Time limit exceeded
8 Execution timed out 1092 ms 45932 KB Time limit exceeded
9 Correct 958 ms 34160 KB Output is correct