oj.uz

Submission #833639

# Submission time Handle Problem Language Result Execution time Memory
833639 2023-08-22T07:19:24 Z yusuf12360 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 179 ms 36844 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, q, timer;
vector<int> ord, mn, stat, h;
vector<vector<int>> par;
vector<vector<pair<int, int>>> adj;
void dfs1(int u=0, int H=0) {
	mn[u]=u; h[u]=H;
	for(auto &p : adj[u])
		dfs1(p.second, H+1), mn[u]=min(mn[u], p.first=mn[p.second]);
}
void dfs2(int u=0) {
	for(auto p : adj[u])
		dfs2(p.second);
	ord[u]=timer--;
}
signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	ord.resize(n+1); adj.resize(n+1);
	par.resize(n+1, vector<int>(20));
	mn.resize(n+1); stat.resize(n+1);
	h.resize(n+1);
	for(int i=1; i<=n; i++) {
		int p; cin >> p;
		adj[p].push_back({i, i});
		par[i][0]=p;
	}
	for(int d=1; d<20; d++)
		for(int i=0; i<=n; i++) par[i][d]=par[par[i][d-1]][d-1];
	dfs1();
	for(auto &p : adj) sort(p.begin(), p.end());
	dfs2();
	priority_queue<pair<int, int>> pq;
	for(int i=0; i<=n; i++) pq.push({ord[i], i});
	while(q--) {
		int type, in; cin >> type >> in;
		if(type==1) {
			int las;
			while(in--) 
				stat[las=pq.top().second]=1, pq.pop();
			cout << las << '\n';
		} else {
			int prev; prev=h[in];
			for(int d=19; d>=0; d--) if(stat[par[in][d]]) in=par[in][d];
			stat[in]=0; pq.push({ord[in], in});
			cout << prev-h[in] << '\n';
		}
	}
	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 86 ms 20952 KB Output is correct
3 Correct 51 ms 20968 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 580 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 4 ms 1676 KB Output is correct
10 Correct 14 ms 5532 KB Output is correct
11 Correct 100 ms 21112 KB Output is correct
12 Correct 50 ms 20960 KB Output is correct
13 Correct 72 ms 20928 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7488 KB Output is correct
2 Correct 135 ms 33484 KB Output is correct
3 Correct 87 ms 30404 KB Output is correct
4 Correct 42 ms 10896 KB Output is correct
5 Correct 41 ms 10832 KB Output is correct
6 Correct 38 ms 10844 KB Output is correct
7 Correct 39 ms 9668 KB Output is correct
8 Correct 24 ms 7468 KB Output is correct
9 Correct 151 ms 33940 KB Output is correct
10 Correct 138 ms 33476 KB Output is correct
11 Correct 105 ms 33504 KB Output is correct
12 Correct 121 ms 31704 KB Output is correct
13 Correct 80 ms 32348 KB Output is correct
14 Correct 74 ms 30408 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 17200 KB Output is correct
2 Correct 149 ms 32564 KB Output is correct
3 Correct 108 ms 29372 KB Output is correct
4 Correct 99 ms 27248 KB Output is correct
5 Correct 95 ms 27116 KB Output is correct
6 Correct 99 ms 27156 KB Output is correct
7 Correct 96 ms 26200 KB Output is correct
8 Correct 117 ms 29424 KB Output is correct
9 Correct 144 ms 34088 KB Output is correct
10 Correct 167 ms 33776 KB Output is correct
11 Correct 152 ms 33776 KB Output is correct
12 Correct 149 ms 32484 KB Output is correct
13 Correct 179 ms 36844 KB Output is correct
14 Correct 103 ms 30788 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 33980 KB Output is correct
2 Correct 141 ms 32524 KB Output is correct
3 Correct 106 ms 36416 KB Output is correct
4 Correct 145 ms 34020 KB Output is correct
5 Correct 139 ms 33780 KB Output is correct
6 Correct 110 ms 33676 KB Output is correct
7 Correct 142 ms 32480 KB Output is correct
8 Correct 91 ms 36352 KB Output is correct
9 Correct 70 ms 30512 KB Output is correct