Submission #110431

#	Time	Username	Problem	Language	Result	Execution time	Memory
110431		wilwxk	Ball Machine (BOI13_ballmachine)	C++11	20.95 / 100	1088 ms	27764 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 tree[MAXN], rtree[MAXN];
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(!s.empty()) {
		int cur= *s.begin();
		int p=dp[cur][0];
		tree[++contv]=cur;
		rtree[cur]=contv;
		gin[p]--;
		if(!gin[p]) s.insert(p);
		s.erase(cur);
	}

	for(int i=1; i<=n; i++) s.insert(i);

	while(q--) {
		int a, x; scanf("%d %d", &a, &x);
		if(a==1) {
			int cur, ind;
			while(x--) {
				ind= *s.begin();
				s.erase(s.begin());
				cur=tree[ind];
				marc[cur]=1;
				// printf("tira %d (%d)\n", cur, ind);
			}
			printf("%d\n", cur);
		}
		else {
			int cur=pula(x);
			int ind=rtree[cur];
			// printf("coloca %d (%d)\n", cur, ind);
			s.insert(ind);
			marc[cur]=0;
			printf("%d\n", prof[x]-prof[cur]);
		}
	}
}

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: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:59: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