Submission #276053

#	Time	Username	Problem	Language	Result	Execution time	Memory
276053		shrek12357	Ball Machine (BOI13_ballmachine)	C++14	28.36 / 100	1101 ms	47568 KiB

ballmachine

#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.23076923076923 / 25
• Subtask 2: 8.571428571428571 / 30
• Subtask 3: 0 / 40
• Subtask 4: 0.5555555555555556 / 5