oj.uz

Submission #870526

# Submission time Handle Problem Language Result Execution time Memory
870526 2023-11-08T07:59:55 Z Amirmohammad_sh Ball Machine (BOI13_ballmachine) C++17
100 / 100
 138 ms 28924 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, lg = 20;
set<int> s;
bool mark[N];
vector<int> adj[N];
int n, q, r, cnt, h[N], mn[N], ft[N], ft1[N], par[N][lg];

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

void dfs1(int v){
	for (int i = 1; i < lg; i++){
		if (par[v][i - 1] != -1) {
			par[v][i] = par[par[v][i - 1]][i - 1];
		}
	}
	for (auto u: adj[v]){
		h[u] = h[v] + 1;
		dfs1(u);
		mn[v] = min(mn[v], mn[u]);
	}
}

int get_par(int v) {
	for (int i = lg - 1; ~i; i--) {
		if (par[v][i] != -1 && mark[par[v][i]]) {
			v = par[v][i];
		}
	}
	return v;
}

void dfs2(int v){
	for (auto u: adj[v]){
		dfs2(u);
	}
	s.insert(cnt);
	ft[v] = cnt;
	ft1[cnt] = v;
	cnt++;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	memset(par, -1, sizeof par);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int p;
		cin >> p;
		mn[i] = i;
		par[i][0] = p;
		adj[p].push_back(i);
		if (p == 0) {
			r = i;
		}
	}
	dfs1(r);
	for (int i = 1; i <= n; i++)  {
		sort(adj[i].begin(), adj[i].end(), cmp);
	}
	dfs2(r);
	while(q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int k, v;
			cin >> k;
			while (k--) {
				v = ft1[*s.begin()];
				mark[v] = true;
				s.erase(ft[v]);
			}
			cout << v << "\n";
		}
		else {
			int v;
			cin >> v;
			int u = get_par(v);
			mark[u] = false;
			s.insert(ft[u]);
			cout << h[v] - h[u] << "\n";
		}
	}
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:76:17: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |    cout << v << "\n";
      |                 ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12120 KB Output is correct
2 Correct 71 ms 17492 KB Output is correct
3 Correct 46 ms 17752 KB Output is correct
4 Correct 2 ms 12124 KB Output is correct
5 Correct 2 ms 12120 KB Output is correct
6 Correct 3 ms 12124 KB Output is correct
7 Correct 3 ms 12124 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 7 ms 12376 KB Output is correct
10 Correct 16 ms 13404 KB Output is correct
11 Correct 83 ms 17748 KB Output is correct
12 Correct 51 ms 17496 KB Output is correct
13 Correct 64 ms 17564 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15444 KB Output is correct
2 Correct 108 ms 23468 KB Output is correct
3 Correct 57 ms 19404 KB Output is correct
4 Correct 47 ms 16084 KB Output is correct
5 Correct 48 ms 16044 KB Output is correct
6 Correct 47 ms 16072 KB Output is correct
7 Correct 55 ms 15296 KB Output is correct
8 Correct 27 ms 15452 KB Output is correct
9 Correct 99 ms 23888 KB Output is correct
10 Correct 112 ms 23592 KB Output is correct
11 Correct 103 ms 23380 KB Output is correct
12 Correct 104 ms 21832 KB Output is correct
13 Correct 71 ms 26192 KB Output is correct
14 Correct 57 ms 19400 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 18012 KB Output is correct
2 Correct 138 ms 22080 KB Output is correct
3 Correct 80 ms 24596 KB Output is correct
4 Correct 72 ms 21356 KB Output is correct
5 Correct 73 ms 21200 KB Output is correct
6 Correct 71 ms 21072 KB Output is correct
7 Correct 70 ms 19796 KB Output is correct
8 Correct 79 ms 24660 KB Output is correct
9 Correct 109 ms 24024 KB Output is correct
10 Correct 129 ms 23632 KB Output is correct
11 Correct 115 ms 23764 KB Output is correct
12 Correct 117 ms 22100 KB Output is correct
13 Correct 132 ms 28924 KB Output is correct
14 Correct 92 ms 19832 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 24148 KB Output is correct
2 Correct 110 ms 22144 KB Output is correct
3 Correct 104 ms 27924 KB Output is correct
4 Correct 109 ms 24132 KB Output is correct
5 Correct 124 ms 23624 KB Output is correct
6 Correct 125 ms 23664 KB Output is correct
7 Correct 132 ms 22544 KB Output is correct
8 Correct 83 ms 27728 KB Output is correct
9 Correct 62 ms 19408 KB Output is correct