oj.uz

답안 #944639

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
944639 2024-03-13T02:22:45 Z tamir1 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 142 ms 28624 KB 
#include<bits/stdc++.h>
#define ll int
using namespace std;
ll i,j,n,q,x,y,root,a[100005],jump[100005][21],p[100005],dist[100005];
set<ll> s;
set<ll> ::iterator it;
vector<ll> v[100005],u;
bitset<100005> ball;
void dfs(ll x){
	a[x]=x;
	for(ll i:v[x]){
		dist[i]=dist[x]+1;
		dfs(i);
		a[x]=min(a[x],a[i]);
	}
}
bool cmp(ll x,ll y){
	return a[x]<a[y];
}
void dfs1(ll x){
	for(ll i:v[x]){
		dfs1(i);
	}
	p[x]=u.size();
	u.push_back(x);
}
ll up(ll x){
	ll i;
	for(i=20;i>=0;i--){
		if(ball[jump[x][i]]) x=jump[x][i];
	}
	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];
		s.insert(i-1);
		if(jump[i][0]==0) root=i;
		else v[jump[i][0]].push_back(i);
	}
	for(j=1;j<=20;j++){
		for(i=1;i<=n;i++){
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}
	dfs(root);
	for(i=1;i<=n;i++){
		sort(v[i].begin(),v[i].end(),cmp);
	}
	dfs1(root);
	while(q--){
		cin >> x >> y;
		if(x==1){
			for(i=1;i<=y;i++){
				it=s.begin();
				x=u[*it];
				ball[x]=1;
				s.erase(it);
			}
			cout << x << "\n";
		}
		else{
			x=up(y);
			ball[x]=0;
			s.insert(p[x]);
			cout << dist[y]-dist[x] << "\n";
		}
	}
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 106 ms 16856 KB Output is correct
3 Correct 52 ms 16852 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 6 ms 4952 KB Output is correct
10 Correct 16 ms 8024 KB Output is correct
11 Correct 76 ms 16880 KB Output is correct
12 Correct 50 ms 16860 KB Output is correct
13 Correct 71 ms 16764 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 10328 KB Output is correct
2 Correct 106 ms 23900 KB Output is correct
3 Correct 60 ms 19956 KB Output is correct
4 Correct 48 ms 11084 KB Output is correct
5 Correct 51 ms 10844 KB Output is correct
6 Correct 48 ms 10884 KB Output is correct
7 Correct 50 ms 10192 KB Output is correct
8 Correct 27 ms 10324 KB Output is correct
9 Correct 114 ms 24524 KB Output is correct
10 Correct 106 ms 23988 KB Output is correct
11 Correct 103 ms 23812 KB Output is correct
12 Correct 99 ms 22024 KB Output is correct
13 Correct 100 ms 25552 KB Output is correct
14 Correct 64 ms 19816 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 15060 KB Output is correct
2 Correct 119 ms 22472 KB Output is correct
3 Correct 82 ms 24008 KB Output is correct
4 Correct 80 ms 20844 KB Output is correct
5 Correct 101 ms 20432 KB Output is correct
6 Correct 74 ms 20428 KB Output is correct
7 Correct 89 ms 19540 KB Output is correct
8 Correct 87 ms 24012 KB Output is correct
9 Correct 130 ms 24468 KB Output is correct
10 Correct 109 ms 24012 KB Output is correct
11 Correct 118 ms 24200 KB Output is correct
12 Correct 108 ms 22480 KB Output is correct
13 Correct 142 ms 28624 KB Output is correct
14 Correct 99 ms 20332 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 24892 KB Output is correct
2 Correct 105 ms 22472 KB Output is correct
3 Correct 91 ms 28264 KB Output is correct
4 Correct 123 ms 24560 KB Output is correct
5 Correct 114 ms 24104 KB Output is correct
6 Correct 104 ms 24008 KB Output is correct
7 Correct 110 ms 22464 KB Output is correct
8 Correct 96 ms 28112 KB Output is correct
9 Correct 61 ms 19788 KB Output is correct