Submission #198014

#	Time	Username	Problem	Language	Result	Execution time	Memory
198014		dndhk	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	222 ms	24904 KiB

ballmachine

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int MAX_N = 100000;
const int MAX_K = 20;

int N, Q, R, p[MAX_N+1];
vector<int> gp[MAX_N+1];
int up[MAX_N+1][MAX_K+1];
vector<int> v;
int num[MAX_N+1], lv[MAX_N+1];
priority_queue<int, vector<int>, greater<int> > pq;
int chk[MAX_N+1];

void dfs(int x){
	up[x][0] = p[x];
	for(int i=1; i<MAX_K; i++){
		up[x][i] = up[up[x][i-1]][i-1];
	}
	for(int i : gp[x]){
		lv[i] = lv[x]+1;
		dfs(i);
	}
	pq.push(v.size());
	num[x] = v.size();
	v.pb(x);
}

int main(){
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=N; i++){
		scanf("%d", &p[i]);
		if(p[i]==0){
			R = i;
		}
	}
	for(int i=1; i<=N; i++){
		if(p[i]==0)	continue;
		if(!chk[i]){
			int n = i;
			while(n!=R){
				if(chk[n])	break;
				gp[p[n]].pb(n);
				chk[n] = true;
				n = p[n];
			}
		}
	}
	for(int i=1; i<=N; i++)	chk[i] = false;
	lv[R] = 1; dfs(R);
	for(int i=1; i<=Q; i++){
		int x, y; scanf("%d%d", &x, &y);
		if(x==1){
			while(y--){
				int n = pq.top(); pq.pop();
				n = v[n];
				chk[n] = true;
				//cout<<n<<" ";
				if(y==0){
					printf("%d\n", n);
				}
			}
		}else{
			x = y;
			for(int i=MAX_K-1; i>=0; i--){
				if(up[y][i]==0)	continue;
				if(chk[up[y][i]]){
					y = up[y][i];
				}
			}
			chk[y] = false;
			pq.push(num[y]);
			printf("%d\n", lv[x]-lv[y]);
		}
	}
	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p[i]);
   ~~~~~^~~~~~~~~~~~~
ballmachine.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

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