oj.uz

Submission #870157

# Submission time Handle Problem Language Result Execution time Memory
870157 2023-11-07T06:09:50 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 144 ms 38092 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 19036 KB Output is correct
2 Correct 81 ms 27208 KB Output is correct
3 Correct 46 ms 27044 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19004 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 20828 KB Output is correct
11 Correct 83 ms 27048 KB Output is correct
12 Correct 47 ms 26980 KB Output is correct
13 Correct 68 ms 26980 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 22620 KB Output is correct
2 Correct 117 ms 34412 KB Output is correct
3 Correct 66 ms 30944 KB Output is correct
4 Correct 45 ms 24244 KB Output is correct
5 Correct 45 ms 23928 KB Output is correct
6 Correct 43 ms 23728 KB Output is correct
7 Correct 44 ms 23224 KB Output is correct
8 Correct 25 ms 22620 KB Output is correct
9 Correct 106 ms 34756 KB Output is correct
10 Correct 107 ms 34432 KB Output is correct
11 Correct 90 ms 34240 KB Output is correct
12 Correct 111 ms 32956 KB Output is correct
13 Correct 63 ms 35784 KB Output is correct
14 Correct 61 ms 30952 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 26724 KB Output is correct
2 Correct 144 ms 33472 KB Output is correct
3 Correct 83 ms 33376 KB Output is correct
4 Correct 79 ms 31100 KB Output is correct
5 Correct 80 ms 30628 KB Output is correct
6 Correct 77 ms 31028 KB Output is correct
7 Correct 86 ms 29796 KB Output is correct
8 Correct 83 ms 33392 KB Output is correct
9 Correct 133 ms 35084 KB Output is correct
10 Correct 129 ms 34496 KB Output is correct
11 Correct 144 ms 35088 KB Output is correct
12 Correct 129 ms 33288 KB Output is correct
13 Correct 132 ms 38092 KB Output is correct
14 Correct 112 ms 31672 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 35116 KB Output is correct
2 Correct 140 ms 33272 KB Output is correct
3 Correct 71 ms 37776 KB Output is correct
4 Correct 125 ms 35012 KB Output is correct
5 Correct 140 ms 34924 KB Output is correct
6 Correct 94 ms 34544 KB Output is correct
7 Correct 127 ms 33444 KB Output is correct
8 Correct 73 ms 37572 KB Output is correct
9 Correct 61 ms 31204 KB Output is correct