Submission #276091

#	Time	Username	Problem	Language	Result	Execution time	Memory
276091		shrek12357	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	613 ms	29648 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];
vector<int> adjList[MAXN];
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;
int balls[MAXN];

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[cur] = true;
				p.pop();
			}
			cout << cur << endl;
		}
		else {
			int curNode = b;
			for (int j = 19; j >= 0; j--) {
				if (balls[anc[curNode][j]]) {
					curNode = anc[curNode][j];
				}
			}
			balls[curNode] = false;
			p.push(make_pair(order[curNode], curNode));
			cout << depth[b] - depth[curNode] << endl;
		}
	}
}

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5