oj.uz

Submission #870235

# Submission time Handle Problem Language Result Execution time Memory
870235 2023-11-07T09:28:18 Z falaz Ball Machine (BOI13_ballmachine) C++17
100 / 100
 164 ms 36808 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'

#define F first 
#define S second

const int N = 1e5 + 15, LOG = 19;
int n, q, par[LOG][N], zr[N], sv[N], t = 1, root;
unordered_map<int, int> mp;
vector<int> adj[N];
bool ch[N];
set<int> s;

void ip() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		zr[i] = i;
		int p;
		cin >> p;
		par[0][i] = p;
		adj[p].push_back(i);
		if (p == 0)
			root = i;
	}
}

void fix_par() {
	for (int j = 1; j < LOG; j++)
		for (int i = 1; i <= n; i++)
			par[j][i] = par[j - 1][par[j - 1][i]];
}

void dfs(int v) {
	for (auto u : adj[v]) {
		dfs(u);
		zr[v] = min(zr[v], zr[u]);
	}
}

void fdfs(int v) {
	for (auto u : adj[v])
		fdfs(u);
	sv[v] = t;
	mp[t] = v;
	s.insert(t);
	t++;
}

bool cmp(int i, int j) {
	return (zr[i] < zr[j]);
}

void fix() {
	for (int i = 1; i <= n; i++) 
		sort(adj[i].begin(), adj[i].end(), cmp);
		
/*	for (int i = 1; i <= n; i++) {
		cout << i << " : ";
		for (auto v : adj[i])
			cout << v << " ";
		cout << endl;
	}*/
}


pair<int, int> get_par(int v) {
	int cnt = 0;
	for (int i = LOG - 1; ~i; i--) {
		if (ch[par[i][v]]) {
			cnt += (1 << i);
			v = par[i][v];
		}
	}
	return (make_pair(cnt, v));
}

void query() {
	while (q--) {
		int qu, f;
		cin >> qu;
		if (qu == 1) {
			cin >> f;
			int v;
			while (f--) {
				v = mp[*s.begin()];
				s.erase(s.begin());
				ch[v] = true;
		//		cout << v << " ";
			}
		//	cout << endl;
			cout << v << endl;
		}
		else {
			cin >> f;
			pair<int, int> ans = get_par(f);
//			cout << ans.F << " " << ans.S << endl;
			ch[ans.S] = false;
			s.insert(sv[ans.S]);
			cout << ans.F << endl;
		}
	}
}

void run() {
	ip();
	fix_par();
	dfs(root);
	fix();
	fdfs(root);
	query();
}

signed main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	run();
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 89 ms 25932 KB Output is correct
3 Correct 46 ms 26000 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 3 ms 19032 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 7 ms 19292 KB Output is correct
10 Correct 16 ms 20568 KB Output is correct
11 Correct 94 ms 25952 KB Output is correct
12 Correct 48 ms 26208 KB Output is correct
13 Correct 70 ms 25980 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 22104 KB Output is correct
2 Correct 144 ms 33148 KB Output is correct
3 Correct 79 ms 30096 KB Output is correct
4 Correct 45 ms 23304 KB Output is correct
5 Correct 54 ms 22968 KB Output is correct
6 Correct 43 ms 22968 KB Output is correct
7 Correct 44 ms 22580 KB Output is correct
8 Correct 29 ms 22108 KB Output is correct
9 Correct 110 ms 33476 KB Output is correct
10 Correct 118 ms 32996 KB Output is correct
11 Correct 93 ms 33016 KB Output is correct
12 Correct 115 ms 31684 KB Output is correct
13 Correct 65 ms 34656 KB Output is correct
14 Correct 64 ms 30172 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 26180 KB Output is correct
2 Correct 127 ms 31936 KB Output is correct
3 Correct 96 ms 32632 KB Output is correct
4 Correct 98 ms 30116 KB Output is correct
5 Correct 77 ms 29856 KB Output is correct
6 Correct 112 ms 30260 KB Output is correct
7 Correct 86 ms 28924 KB Output is correct
8 Correct 81 ms 32536 KB Output is correct
9 Correct 128 ms 33692 KB Output is correct
10 Correct 156 ms 33308 KB Output is correct
11 Correct 134 ms 33268 KB Output is correct
12 Correct 141 ms 31940 KB Output is correct
13 Correct 140 ms 36808 KB Output is correct
14 Correct 113 ms 30320 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 33828 KB Output is correct
2 Correct 124 ms 32072 KB Output is correct
3 Correct 77 ms 36704 KB Output is correct
4 Correct 136 ms 33732 KB Output is correct
5 Correct 121 ms 33220 KB Output is correct
6 Correct 95 ms 33260 KB Output is correct
7 Correct 164 ms 31936 KB Output is correct
8 Correct 76 ms 36556 KB Output is correct
9 Correct 65 ms 30180 KB Output is correct