oj.uz

답안 #536493

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
536493 2022-03-13T12:30:40 Z new_acc Ball Machine (BOI13_ballmachine) C++14
100 / 100
 227 ms 33024 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
vi graf[N];
bitset<N>vis;
int pre[N],dep[N],jump[N][20],pod[N],odw[N],l;
set<int>s;
void dfs(int v,int o){
	jump[v][0]=o;
	for(int i=1;i<=19;i++) jump[v][i]=jump[jump[v][i-1]][i-1];
	dep[v]=dep[o]+1;
	pod[v]=v;
	for(auto u:graf[v]) dfs(u,v),pod[v]=min(pod[v],pod[u]);
}
void dfs2(int v){
	vector<pair<int,int> >curr;
	for(auto u:graf[v]) curr.push_back({pod[u],u});
	sort(curr.begin(),curr.end());
	for(auto u:curr) dfs2(u.se);
	pre[v]=++l,odw[l]=v;
	s.insert(l);
}
int Find(int v){
	for(int i=19;i>=0;i--)
		if(vis[jump[v][i]]) v=jump[v][i];
	return v;
}
void solve(){
	int n,q;
	cin>>n>>q;
	int kk=0;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		if(a==0) kk=i;
		else graf[a].push_back(i);
	}
	dfs(kk,kk),dfs2(kk);
	while(q--){
		int a,b;
		cin>>a>>b;
			if(a==1){
				int last=0;
			for(int j=1;j<=b;j++){
				auto it=s.begin();
				last=odw[*it];
				vis[last]=1;
				s.erase(it);
			}
			cout<<last<<"\n";
		}else{
			int num=Find(b);
			cout<<dep[b]-dep[num]<<"\n";
			vis[num]=0,s.insert(pre[num]);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 126 ms 13056 KB Output is correct
3 Correct 70 ms 13296 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct
9 Correct 8 ms 3284 KB Output is correct
10 Correct 27 ms 5280 KB Output is correct
11 Correct 125 ms 13064 KB Output is correct
12 Correct 72 ms 13248 KB Output is correct
13 Correct 124 ms 13328 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 8376 KB Output is correct
2 Correct 163 ms 25288 KB Output is correct
3 Correct 97 ms 18388 KB Output is correct
4 Correct 60 ms 9608 KB Output is correct
5 Correct 98 ms 9604 KB Output is correct
6 Correct 68 ms 9556 KB Output is correct
7 Correct 58 ms 8084 KB Output is correct
8 Correct 35 ms 8396 KB Output is correct
9 Correct 158 ms 25596 KB Output is correct
10 Correct 201 ms 25236 KB Output is correct
11 Correct 146 ms 25332 KB Output is correct
12 Correct 158 ms 21652 KB Output is correct
13 Correct 132 ms 29328 KB Output is correct
14 Correct 122 ms 18392 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 14156 KB Output is correct
2 Correct 192 ms 22380 KB Output is correct
3 Correct 157 ms 26848 KB Output is correct
4 Correct 129 ms 21068 KB Output is correct
5 Correct 121 ms 20924 KB Output is correct
6 Correct 112 ms 20800 KB Output is correct
7 Correct 136 ms 18300 KB Output is correct
8 Correct 155 ms 26788 KB Output is correct
9 Correct 178 ms 25936 KB Output is correct
10 Correct 217 ms 25496 KB Output is correct
11 Correct 227 ms 25484 KB Output is correct
12 Correct 188 ms 22316 KB Output is correct
13 Correct 209 ms 33024 KB Output is correct
14 Correct 162 ms 18444 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 25860 KB Output is correct
2 Correct 181 ms 22376 KB Output is correct
3 Correct 155 ms 32880 KB Output is correct
4 Correct 176 ms 25924 KB Output is correct
5 Correct 210 ms 25472 KB Output is correct
6 Correct 170 ms 25424 KB Output is correct
7 Correct 191 ms 22348 KB Output is correct
8 Correct 165 ms 32748 KB Output is correct
9 Correct 97 ms 18500 KB Output is correct