제출 #67978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67978		thebes	Ball Machine (BOI13_ballmachine)	C++14	16.78 / 100	206 ms	69244 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];
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);
	}
	dfs(1), ord(1);
	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;
}

컴파일 시 표준 에러 (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:30: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: 3.8461538461538463 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 0 / 40
• Subtask 4: 2.2222222222222223 / 5