oj.uz

Submission #967329

# Submission time Handle Problem Language Result Execution time Memory
967329 2024-04-22T01:43:27 Z penguin133 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 334 ms 59728 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
int n, q;
vector<int>v[200005];
int sub[200005];
deque<int>dq;
priority_queue<int, vector<int>, greater<int> > pq;
void dfs(int x){
	sub[x] = min(sub[x], x);
	for(auto i : v[x]){
		dfs(i);
		sub[x] = min(sub[x], sub[i]);
	}
}
bool cmp(int a, int b){
	return sub[a] < sub[b];
}
void dfs2(int x){
	vector<int>tmp;
	for(auto i : v[x])tmp.push_back(i);
	sort(tmp.begin(), tmp.end(), cmp);
	for(auto i : tmp)dfs2(i);
	if(x)dq.push_back(x);
}
int par[20][200005];
int vis[200005];
void dfs3(int x, int p){
	if(x)par[0][x] = p;
	for(auto i : v[x]){
		dfs3(i, x);
	}
}
int c(int x, int k){
	for(int i=0;i<=19;i++){
		if(k >> i & 1)x = par[i][x];
		if(x == -1)return 0;
	}
	return vis[x];
}
int lnk[200005];
void solve(){
	cin >> n >> q;
	for(int i=1;i<=n;i++){
		int x;cin >> x;
		v[x].push_back(i);
	}
	for(int i=1;i<=n;i++)sub[i] = 1e9;
	dfs(0);
	dfs2(0);
	dfs3(0, -1);
	for(int i=1;i<=19;i++)for(int j=1;j<=n;j++)par[i][j] = par[i-1][par[i-1][j]];
	for(int i=0;i<n;i++)pq.push(i), lnk[dq[i]] = i;
	while(q--){
		int x;cin >> x;
		if(x == 1){
			int k;cin >> k;
			int tmp;
			for(int i=0;i<k;i++){
				tmp = dq[pq.top()];
				pq.pop();
				vis[tmp] = 1;
			}
			cout << tmp << '\n';
		}
		else{
			int k;cin >> k;
			int s = 1, e = n, ans = 0;
			while(s <= e){
				int m = (s + e)/2;
				if(c(k, m))ans = m, s = m + 1;
				else e = m - 1;
			}
			int tmp = k;
			for(int i=0;i<=19;i++)if(ans >> i & 1)tmp = par[i][tmp];
			vis[tmp ] =0;
			pq.push(lnk[tmp]);
			cout << ans << '\n';
		}
	}
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message

ballmachine.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 | main(){
      | ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 40796 KB Output is correct
2 Correct 124 ms 44616 KB Output is correct
3 Correct 61 ms 44500 KB Output is correct
4 Correct 6 ms 40792 KB Output is correct
5 Correct 7 ms 40796 KB Output is correct
6 Correct 7 ms 40988 KB Output is correct
7 Correct 7 ms 41020 KB Output is correct
8 Correct 7 ms 40988 KB Output is correct
9 Correct 12 ms 41304 KB Output is correct
10 Correct 25 ms 42108 KB Output is correct
11 Correct 109 ms 44764 KB Output is correct
12 Correct 50 ms 44756 KB Output is correct
13 Correct 98 ms 44544 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 44880 KB Output is correct
2 Correct 191 ms 52184 KB Output is correct
3 Correct 60 ms 46020 KB Output is correct
4 Correct 80 ms 45120 KB Output is correct
5 Correct 96 ms 44624 KB Output is correct
6 Correct 81 ms 44648 KB Output is correct
7 Correct 80 ms 43724 KB Output is correct
8 Correct 39 ms 44760 KB Output is correct
9 Correct 167 ms 52144 KB Output is correct
10 Correct 177 ms 51984 KB Output is correct
11 Correct 137 ms 51932 KB Output is correct
12 Correct 186 ms 48972 KB Output is correct
13 Correct 80 ms 57172 KB Output is correct
14 Correct 63 ms 45768 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 46668 KB Output is correct
2 Correct 281 ms 49336 KB Output is correct
3 Correct 205 ms 55512 KB Output is correct
4 Correct 163 ms 50028 KB Output is correct
5 Correct 171 ms 49488 KB Output is correct
6 Correct 130 ms 49488 KB Output is correct
7 Correct 135 ms 47448 KB Output is correct
8 Correct 223 ms 55376 KB Output is correct
9 Correct 311 ms 52704 KB Output is correct
10 Correct 236 ms 52088 KB Output is correct
11 Correct 275 ms 52208 KB Output is correct
12 Correct 228 ms 49228 KB Output is correct
13 Correct 334 ms 59728 KB Output is correct
14 Correct 91 ms 45896 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 52772 KB Output is correct
2 Correct 274 ms 49720 KB Output is correct
3 Correct 81 ms 58960 KB Output is correct
4 Correct 277 ms 52484 KB Output is correct
5 Correct 238 ms 52128 KB Output is correct
6 Correct 154 ms 52032 KB Output is correct
7 Correct 235 ms 49392 KB Output is correct
8 Correct 82 ms 59168 KB Output is correct
9 Correct 62 ms 45776 KB Output is correct