Submission #110491

#	Time	Username	Problem	Language	Result	Execution time	Memory
110491		wilwxk	Ball Machine (BOI13_ballmachine)	C++11	20.95 / 100	1090 ms	20840 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
const int LOGN=22;
vector<int> g[MAXN];
int dp[MAXN][LOGN];
int prof[MAXN], gin[MAXN];
int marc[MAXN];
set<int> s;
int n, q, root;
int contv;

void dfs(int cur, int p) {
	for(auto viz : g[cur]) {
		if(viz==p) continue;
		dp[viz][0]=cur;
		gin[cur]++;
		prof[viz]=prof[cur]+1;
		dfs(viz, cur);
	}
}

int pula(int cur) {
	for(int i=LOGN-1; i>=0; i--) {
		if(marc[dp[cur][i]]) cur=dp[cur][i];
	}
	return cur;
}

int main() {
	scanf("%d %d", &n, &q);
	for(int i=1; i<=n; i++) {
		int a; scanf("%d", &a);
		if(a==0) root=i;
		else g[a].push_back(i), g[i].push_back(a);
	}

	dfs(root, root);
	for(int i=1; i<=n; i++) if(!gin[i]) s.insert(i);
	for(int i=1; i<LOGN; i++) {
		for(int j=1; j<=n; j++) dp[j][i]=dp[dp[j][i-1]][i-1];
	}

	while(q--) {
		int a, x; scanf("%d %d", &a, &x);
		if(a==1) {
			int cur, p;
			while(x--) {
				cur= *s.begin();
				p=dp[cur][0];
				s.erase(s.begin());
				marc[cur]=1;
				gin[p]--;
				if(!gin[p]) s.insert(p);
			}
			printf("%d\n", cur);
		}
		else {
			int cur=pula(x);
			int p=dp[cur][0];
			marc[cur]=0;
			gin[p]++;
			s.erase(p);
			s.insert(cur);
			printf("%d\n", prof[x]-prof[cur]);
		}
	}
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:32: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:34:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a);
          ~~~~~^~~~~~~~~~
ballmachine.cpp:46:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, x; scanf("%d %d", &a, &x);
             ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 8.571428571428571 / 40
• Subtask 4: 1.6666666666666667 / 5