oj.uz

답안 #943989

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
943989 2024-03-12T06:16:12 Z tamir1 Ball Machine (BOI13_ballmachine) C++17
0 / 100
 13 ms 21852 KB 
#include<bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
int root,n,q,i,j,type,x,a[100005],jump[20][100005],sz[100005],dist[100005];
vector<int> v[100005];
bitset<100005> ball;
void dfs(int k){
	a[k]=k;
	sz[k]=1;
	for(int i:v[k]){
		dist[i]=dist[k]+1;
		dfs(i);
		a[k]=min(a[k],a[i]);
		sz[k]+=sz[i];
	}
}
int find(int x){
	if(ball[jump[x][0]]==0) return x;
	return find(jump[x][0]);
}
int update(int x){
	int mx=1e8,idx=0;
	for(int i:v[x]){
		if(a[i]<mx && !ball[i]){
			mx=a[i];
			idx=i;
		}
	}
	if(idx!=0) return update(idx);
	else{
		ball[x]=1;
		return x;
	}
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> q;
	for(i=1;i<=n;i++){
		cin >> jump[i][0];
		if(jump[i][0]==0) root=i;
		else v[jump[i][0]].push_back(i);
	}
	dfs(root);
	for(j=1;j<=18;j++){
		for(i=1;i<=n;i++){
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}
	while(q--){
		cin >> type >> x;
		if(type==1){
			for(i=1;i<=x;i++){
				type=update(1);
			}
			cout << type << "\n";
		}
		else{
			type=find(x);
			ball[type]=0;
			cout << dist[x]-dist[type] << "\n";
		}
	}
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 21596 KB Execution killed with signal 11
2 Runtime error 10 ms 21728 KB Execution killed with signal 11
3 Runtime error 10 ms 21596 KB Execution killed with signal 11
4 Incorrect 2 ms 10844 KB Output isn't correct
5 Runtime error 10 ms 21596 KB Execution killed with signal 11
6 Runtime error 10 ms 21596 KB Execution killed with signal 11
7 Runtime error 10 ms 21644 KB Execution killed with signal 11
8 Runtime error 10 ms 21596 KB Execution killed with signal 11
9 Runtime error 10 ms 21596 KB Execution killed with signal 11
10 Runtime error 10 ms 21592 KB Execution killed with signal 11
11 Runtime error 11 ms 21596 KB Execution killed with signal 11
12 Runtime error 12 ms 21596 KB Execution killed with signal 11
13 Runtime error 10 ms 21596 KB Execution killed with signal 11

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 21596 KB Execution killed with signal 11
2 Runtime error 13 ms 21852 KB Execution killed with signal 11
3 Runtime error 11 ms 21596 KB Execution killed with signal 11
4 Runtime error 10 ms 21596 KB Execution killed with signal 11
5 Runtime error 10 ms 21592 KB Execution killed with signal 11
6 Runtime error 10 ms 21596 KB Execution killed with signal 11
7 Runtime error 10 ms 21596 KB Execution killed with signal 11
8 Runtime error 10 ms 21596 KB Execution killed with signal 11
9 Runtime error 12 ms 21592 KB Execution killed with signal 11
10 Runtime error 10 ms 21596 KB Execution killed with signal 11
11 Runtime error 13 ms 21596 KB Execution killed with signal 11
12 Runtime error 10 ms 21648 KB Execution killed with signal 11
13 Runtime error 10 ms 21592 KB Execution killed with signal 11
14 Runtime error 10 ms 21644 KB Execution killed with signal 11

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 21592 KB Execution killed with signal 11
2 Runtime error 10 ms 21596 KB Execution killed with signal 11
3 Runtime error 10 ms 21596 KB Execution killed with signal 11
4 Runtime error 10 ms 21600 KB Execution killed with signal 11
5 Runtime error 12 ms 21632 KB Execution killed with signal 11
6 Runtime error 10 ms 21788 KB Execution killed with signal 11
7 Runtime error 10 ms 21848 KB Execution killed with signal 11
8 Runtime error 10 ms 21592 KB Execution killed with signal 11
9 Runtime error 10 ms 21596 KB Execution killed with signal 11
10 Runtime error 13 ms 21596 KB Execution killed with signal 11
11 Runtime error 10 ms 21596 KB Execution killed with signal 11
12 Runtime error 10 ms 21596 KB Execution killed with signal 11
13 Runtime error 10 ms 21648 KB Execution killed with signal 11
14 Runtime error 10 ms 21596 KB Execution killed with signal 11

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 21596 KB Execution killed with signal 11
2 Runtime error 10 ms 21596 KB Execution killed with signal 11
3 Runtime error 10 ms 21596 KB Execution killed with signal 11
4 Runtime error 11 ms 21596 KB Execution killed with signal 11
5 Runtime error 11 ms 21596 KB Execution killed with signal 11
6 Runtime error 10 ms 21596 KB Execution killed with signal 11
7 Runtime error 10 ms 21596 KB Execution killed with signal 11
8 Runtime error 10 ms 21592 KB Execution killed with signal 11
9 Runtime error 13 ms 21848 KB Execution killed with signal 11