Submission #67982

#	Time	Username	Problem	Language	Result	Execution time	Memory
67982		thebes	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	253 ms	27988 KiB

ballmachine

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

const int MN=1e5+5,LG=19;
int sp[MN][LG], N, Q, i, j, x, y, mn[MN], p[MN], nxt, fl[MN], rt;
priority_queue<tuple<int,int>> q;
vector<int> adj[MN];
int dfs(int n){
	mn[n] = n;
	for(auto v : adj[n])
		mn[n] = min(mn[n], dfs(v));
	return mn[n];
}
void ord(int n){
	sort(adj[n].begin(),adj[n].end(),[](int i,int j){return mn[i]<mn[j];});
	for(auto v : adj[n]) ord(v);
	p[n] = nxt--; q.push({p[n],n});
}
int main(){
	for(scanf("%d%d",&N,&Q),i=1;i<=N;i++){
		scanf("%d",&x); sp[i][0]=x;
		adj[x].push_back(i);
		if(x == 0) rt = i;
	}
	dfs(rt), ord(rt);
	for(j=1;j<LG;j++){
		for(i=1;i<=N;i++)
			sp[i][j]=sp[sp[i][j-1]][j-1];
	}
	for(;Q;Q--){
		scanf("%d%d",&x,&y);
		if(x == 1){
			int ans = 0;
			while(q.size()&&y){
				fl[get<1>(q.top())]=1;
				ans=get<1>(q.top()); q.pop(); y--;
			}
			printf("%d\n",ans);
		}
		else{
			int ans = 0;
			for(i=LG-1;i>=0;i--)
				if(fl[sp[y][i]]) ans+=1<<i, y=sp[y][i];
			printf("%d\n",ans);
			fl[y] = 0; q.push({p[y],y});
		}
	}
	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:20:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(scanf("%d%d",&N,&Q),i=1;i<=N;i++){
      ~~~~~~~~~~~~~~~~~~~^~~~
ballmachine.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x); sp[i][0]=x;
   ~~~~~^~~~~~~~~
ballmachine.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~

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