oj.uz

답안 #67982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67982 2018-08-15T16:29:23 Z thebes Ball Machine (BOI13_ballmachine) C++14
100 / 100
 253 ms 27988 KB 
#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

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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 127 ms 10984 KB Output is correct
3 Correct 83 ms 10984 KB Output is correct
4 Correct 4 ms 10984 KB Output is correct
5 Correct 5 ms 10984 KB Output is correct
6 Correct 5 ms 10984 KB Output is correct
7 Correct 5 ms 10984 KB Output is correct
8 Correct 7 ms 10984 KB Output is correct
9 Correct 12 ms 10984 KB Output is correct
10 Correct 30 ms 10984 KB Output is correct
11 Correct 115 ms 11124 KB Output is correct
12 Correct 77 ms 11124 KB Output is correct
13 Correct 103 ms 11140 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 11140 KB Output is correct
2 Correct 168 ms 20796 KB Output is correct
3 Correct 97 ms 20796 KB Output is correct
4 Correct 83 ms 20796 KB Output is correct
5 Correct 85 ms 20796 KB Output is correct
6 Correct 72 ms 20796 KB Output is correct
7 Correct 79 ms 20796 KB Output is correct
8 Correct 48 ms 20796 KB Output is correct
9 Correct 174 ms 21196 KB Output is correct
10 Correct 229 ms 21196 KB Output is correct
11 Correct 190 ms 21196 KB Output is correct
12 Correct 195 ms 21196 KB Output is correct
13 Correct 158 ms 24532 KB Output is correct
14 Correct 102 ms 24532 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 24532 KB Output is correct
2 Correct 196 ms 24532 KB Output is correct
3 Correct 165 ms 24532 KB Output is correct
4 Correct 152 ms 24532 KB Output is correct
5 Correct 120 ms 24532 KB Output is correct
6 Correct 121 ms 24532 KB Output is correct
7 Correct 120 ms 24532 KB Output is correct
8 Correct 150 ms 24532 KB Output is correct
9 Correct 232 ms 24532 KB Output is correct
10 Correct 235 ms 24532 KB Output is correct
11 Correct 188 ms 24532 KB Output is correct
12 Correct 221 ms 24532 KB Output is correct
13 Correct 253 ms 27988 KB Output is correct
14 Correct 154 ms 27988 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 27988 KB Output is correct
2 Correct 205 ms 27988 KB Output is correct
3 Correct 139 ms 27988 KB Output is correct
4 Correct 243 ms 27988 KB Output is correct
5 Correct 231 ms 27988 KB Output is correct
6 Correct 199 ms 27988 KB Output is correct
7 Correct 213 ms 27988 KB Output is correct
8 Correct 211 ms 27988 KB Output is correct
9 Correct 111 ms 27988 KB Output is correct