Submission #30530

#	Time	Username	Problem	Language	Result	Execution time	Memory
30530		RezwanArefin01	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	289 ms	22100 KiB

ballmachine

//Bismillahir Rahmanir Rahim
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
vector<int> adj[maxn], post; 
int prior[maxn], dep[maxn], par[maxn][18];
bool has[maxn]; 
int MinDfs(int u) {
	prior[u] = u; 
	for(int v : adj[u]) {
		dep[v] = dep[u] + 1;
		prior[u] = min(prior[u], MinDfs(v)); 
	}
	sort(adj[u].begin(), adj[u].end(), [](int &a, int &b) { return prior[a] < prior[b]; } ); 
	return prior[u];
} 
void postDfs(int u) { 
	for(int i = 1; i <= 17; i++) 
		if(par[u][i-1]) 
			par[u][i] = par[par[u][i-1]][i-1]; 

	if(!adj[u].size()) { post.push_back(u); return; }
	for(int v : adj[u]) postDfs(v); 
	post.push_back(u);
}

struct node{
	int u, prior; 
	bool operator < (const node &p) const {
		return prior > p.prior; 
	}
};

int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	int n, q, root; 
	scanf("%d %d", &n, &q); 
	for(int i = 1; i <= n; i++) {
		int p; scanf("%d", &p); 
		if(p == 0) root = i;
		adj[p].push_back(i);  
		par[i][0] = p;
	} 
	MinDfs(root); 
	postDfs(root); 
	priority_queue<node> Q; 
	for(int i = 0; i < n; i++) {
		Q.push({post[i], i});
		prior[post[i]] = i;
		has[post[i]] = 0;
	}
	while(q--) {
		int c, x; 
		scanf("%d %d", &c, &x); 
		if(c == 1) {
			node u; 
			while(x--) {
				u = Q.top();
				has[u.u] = 1;
				Q.pop();  
			} printf("%d\n", u.u);
		} else {
			int y = x; 
			for(int i = 17; i >= 0; i--) if(par[y][i]) {
				if(has[par[y][i]]) y = par[y][i];
			}
			has[y] = 0;
			printf("%d\n",dep[x] - dep[y]);
			Q.push({y, prior[y]}); 
		}
	}
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main(int, const char**)':
ballmachine.cpp:40:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q); 
                        ^
ballmachine.cpp:42:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p; scanf("%d", &p); 
                         ^
ballmachine.cpp:57:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &c, &x); 
                         ^
ballmachine.cpp:48:15: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  postDfs(root); 
               ^

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