답안 #943994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
943994	2024-03-12T06:19:06 Z	tamir1	Ball Machine (BOI13_ballmachine)	C++17	1.92308 / 100	14 ms	21960 KB

ballmachine

#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],dist[100005];
vector<int> v[100005];
bitset<100005> ball;
void dfs(int k){
	a[k]=k;
	for(int i:v[k]){
		dist[i]=dist[k]+1;
		dfs(i);
		a[k]=min(a[k],a[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);
	while(q--){
		cin >> type >> x;
		if(type==1){
			for(i=1;i<=x;i++){
				type=update(root);
			}
			cout << type << "\n";
		}
		else{
			type=find(x);
			ball[type]=0;
			cout << dist[x]-dist[type] << "\n";
		}
	}
}

Subtask #1

1.92307692308 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	13 ms	21596 KB	Execution killed with signal 11
2	Runtime error	10 ms	21652 KB	Execution killed with signal 11
3	Runtime error	11 ms	21596 KB	Execution killed with signal 11
4	Correct	2 ms	10844 KB	Output is correct
5	Runtime error	14 ms	21644 KB	Execution killed with signal 11
6	Runtime error	11 ms	21600 KB	Execution killed with signal 11
7	Runtime error	10 ms	21608 KB	Execution killed with signal 11
8	Runtime error	11 ms	21668 KB	Execution killed with signal 11
9	Runtime error	11 ms	21592 KB	Execution killed with signal 11
10	Runtime error	11 ms	21596 KB	Execution killed with signal 11
11	Runtime error	10 ms	21796 KB	Execution killed with signal 11
12	Runtime error	10 ms	21596 KB	Execution killed with signal 11
13	Runtime error	10 ms	21592 KB	Execution killed with signal 11

Subtask #2

0 / 30.0

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

Subtask #3

0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	10 ms	21604 KB	Execution killed with signal 11
2	Runtime error	12 ms	21604 KB	Execution killed with signal 11
3	Runtime error	13 ms	21604 KB	Execution killed with signal 11
4	Runtime error	10 ms	21584 KB	Execution killed with signal 11
5	Runtime error	13 ms	21604 KB	Execution killed with signal 11
6	Runtime error	10 ms	21596 KB	Execution killed with signal 11
7	Runtime error	10 ms	21684 KB	Execution killed with signal 11
8	Runtime error	13 ms	21648 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	10 ms	21584 KB	Execution killed with signal 11
12	Runtime error	10 ms	21596 KB	Execution killed with signal 11
13	Runtime error	9 ms	21596 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	10 ms	21648 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	21596 KB	Execution killed with signal 11
5	Runtime error	14 ms	21960 KB	Execution killed with signal 11
6	Runtime error	10 ms	21592 KB	Execution killed with signal 11
7	Runtime error	11 ms	21596 KB	Execution killed with signal 11
8	Runtime error	13 ms	21596 KB	Execution killed with signal 11
9	Runtime error	10 ms	21596 KB	Execution killed with signal 11