oj.uz

답안 #198014

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198014 2020-01-24T13:26:27 Z dndhk Ball Machine (BOI13_ballmachine) C++14
100 / 100
 222 ms 24904 KB 
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int MAX_N = 100000;
const int MAX_K = 20;

int N, Q, R, p[MAX_N+1];
vector<int> gp[MAX_N+1];
int up[MAX_N+1][MAX_K+1];
vector<int> v;
int num[MAX_N+1], lv[MAX_N+1];
priority_queue<int, vector<int>, greater<int> > pq;
int chk[MAX_N+1];

void dfs(int x){
	up[x][0] = p[x];
	for(int i=1; i<MAX_K; i++){
		up[x][i] = up[up[x][i-1]][i-1];
	}
	for(int i : gp[x]){
		lv[i] = lv[x]+1;
		dfs(i);
	}
	pq.push(v.size());
	num[x] = v.size();
	v.pb(x);
}

int main(){
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=N; i++){
		scanf("%d", &p[i]);
		if(p[i]==0){
			R = i;
		}
	}
	for(int i=1; i<=N; i++){
		if(p[i]==0)	continue;
		if(!chk[i]){
			int n = i;
			while(n!=R){
				if(chk[n])	break;
				gp[p[n]].pb(n);
				chk[n] = true;
				n = p[n];
			}
		}
	}
	for(int i=1; i<=N; i++)	chk[i] = false;
	lv[R] = 1; dfs(R);
	for(int i=1; i<=Q; i++){
		int x, y; scanf("%d%d", &x, &y);
		if(x==1){
			while(y--){
				int n = pq.top(); pq.pop();
				n = v[n];
				chk[n] = true;
				//cout<<n<<" ";
				if(y==0){
					printf("%d\n", n);
				}
			}
		}else{
			x = y;
			for(int i=MAX_K-1; i>=0; i--){
				if(up[y][i]==0)	continue;
				if(chk[up[y][i]]){
					y = up[y][i];
				}
			}
			chk[y] = false;
			pq.push(num[y]);
			printf("%d\n", lv[x]-lv[y]);
		}
	}
	return 0;
}

Compilation message

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:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p[i]);
   ~~~~~^~~~~~~~~~~~~
ballmachine.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 112 ms 12148 KB Output is correct
3 Correct 75 ms 12272 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 11 ms 3320 KB Output is correct
10 Correct 24 ms 4988 KB Output is correct
11 Correct 115 ms 12276 KB Output is correct
12 Correct 77 ms 12276 KB Output is correct
13 Correct 104 ms 12268 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 7416 KB Output is correct
2 Correct 185 ms 20216 KB Output is correct
3 Correct 86 ms 16152 KB Output is correct
4 Correct 75 ms 8492 KB Output is correct
5 Correct 75 ms 8440 KB Output is correct
6 Correct 72 ms 8444 KB Output is correct
7 Correct 70 ms 7544 KB Output is correct
8 Correct 44 ms 7288 KB Output is correct
9 Correct 164 ms 20556 KB Output is correct
10 Correct 193 ms 20244 KB Output is correct
11 Correct 168 ms 20092 KB Output is correct
12 Correct 172 ms 18156 KB Output is correct
13 Correct 114 ms 22008 KB Output is correct
14 Correct 89 ms 16024 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 11764 KB Output is correct
2 Correct 195 ms 18664 KB Output is correct
3 Correct 133 ms 20172 KB Output is correct
4 Correct 156 ms 16964 KB Output is correct
5 Correct 132 ms 16616 KB Output is correct
6 Correct 132 ms 16632 KB Output is correct
7 Correct 123 ms 15252 KB Output is correct
8 Correct 133 ms 20140 KB Output is correct
9 Correct 170 ms 20788 KB Output is correct
10 Correct 208 ms 20228 KB Output is correct
11 Correct 200 ms 20204 KB Output is correct
12 Correct 193 ms 18700 KB Output is correct
13 Correct 222 ms 24904 KB Output is correct
14 Correct 123 ms 16344 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 20744 KB Output is correct
2 Correct 197 ms 18720 KB Output is correct
3 Correct 129 ms 24376 KB Output is correct
4 Correct 178 ms 20716 KB Output is correct
5 Correct 204 ms 20208 KB Output is correct
6 Correct 174 ms 20320 KB Output is correct
7 Correct 192 ms 18668 KB Output is correct
8 Correct 127 ms 24396 KB Output is correct
9 Correct 88 ms 16020 KB Output is correct