oj.uz

Submission #385666

# Submission time Handle Problem Language Result Execution time Memory
385666 2021-04-04T17:07:13 Z wind_reaper Ball Machine (BOI13_ballmachine) C++17
100 / 100
 731 ms 26852 KB 
#include <bits/stdc++.h>

using namespace std;

const int MXN = 100005;
const int lg = 20;
const int INF = 100000000;

vector<int> g[MXN];
int depth[MXN], up[lg][MXN], pos[MXN], counter = 0;
vector<int> subtreemin(MXN, INF), order;

void gmin(int node){
	subtreemin[node] = node;
	for(int v : g[node]){
		gmin(v);
		subtreemin[node] = min(subtreemin[node], subtreemin[v]);
	}
}

void dfs(int node, int par){
	depth[node] = depth[par] + 1;

	up[0][node] = par;
	for(int i = 1; i < lg; i++)
		up[i][node] = up[i-1][up[i-1][node]];

	sort(g[node].begin(), g[node].end(), [&](int l, int r){
		return subtreemin[l] < subtreemin[r];
	});

	for(int v : g[node]){
		dfs(v, node);
	}

	order.push_back(node);
	pos[node] = counter++;
}

int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int n, q;
	cin >> n >> q;

	int root;
	
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		if(x == 0){
			root = i;
			continue;
		}
		--x;
		g[x].push_back(i);
	}

	gmin(root);

	dfs(root, root);

	set<int> next;
	for(int i = 0; i < n; i++)
		next.insert(i);

	for(int _ = 0; _ < q; _++){
		int t, x;
		cin >> t >> x;
		if(t == 1){
			int res;
			for(int i = 0; i < x; i++){
				res = order[*next.begin()];
				next.erase(next.begin());
			}
			cout << res + 1 << '\n';
		}
		else{
			--x;
			int v = x;
			for(int i = lg-1; i >= 0; --i){
				if(up[i][x] != x && next.find(pos[up[i][x]]) == next.end())
					x = up[i][x];
			}
			next.insert(pos[x]);
			cout << depth[v] - depth[x] << '\n';
		}
	}
	return 0; 
}

Compilation message

ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:77:23: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |    cout << res + 1 << '\n';
      |                       ^~~~
ballmachine.cpp:62:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |  dfs(root, root);
      |  ~~~^~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3180 KB Output is correct
2 Correct 396 ms 13416 KB Output is correct
3 Correct 177 ms 13544 KB Output is correct
4 Correct 4 ms 3180 KB Output is correct
5 Correct 3 ms 3180 KB Output is correct
6 Correct 5 ms 3308 KB Output is correct
7 Correct 4 ms 3308 KB Output is correct
8 Correct 4 ms 3308 KB Output is correct
9 Correct 18 ms 3820 KB Output is correct
10 Correct 43 ms 5740 KB Output is correct
11 Correct 447 ms 13416 KB Output is correct
12 Correct 169 ms 13544 KB Output is correct
13 Correct 366 ms 13564 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 7660 KB Output is correct
2 Correct 673 ms 22124 KB Output is correct
3 Correct 198 ms 18536 KB Output is correct
4 Correct 198 ms 9068 KB Output is correct
5 Correct 277 ms 8940 KB Output is correct
6 Correct 256 ms 8940 KB Output is correct
7 Correct 242 ms 8172 KB Output is correct
8 Correct 79 ms 7660 KB Output is correct
9 Correct 518 ms 22732 KB Output is correct
10 Correct 659 ms 22124 KB Output is correct
11 Correct 500 ms 22124 KB Output is correct
12 Correct 640 ms 20196 KB Output is correct
13 Correct 204 ms 23912 KB Output is correct
14 Correct 197 ms 18300 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 13040 KB Output is correct
2 Correct 664 ms 20844 KB Output is correct
3 Correct 342 ms 21996 KB Output is correct
4 Correct 312 ms 18916 KB Output is correct
5 Correct 397 ms 18536 KB Output is correct
6 Correct 416 ms 18408 KB Output is correct
7 Correct 414 ms 17532 KB Output is correct
8 Correct 365 ms 22124 KB Output is correct
9 Correct 540 ms 22760 KB Output is correct
10 Correct 681 ms 22248 KB Output is correct
11 Correct 660 ms 22504 KB Output is correct
12 Correct 612 ms 20716 KB Output is correct
13 Correct 607 ms 26852 KB Output is correct
14 Correct 377 ms 18408 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 22788 KB Output is correct
2 Correct 683 ms 20716 KB Output is correct
3 Correct 227 ms 26596 KB Output is correct
4 Correct 514 ms 22764 KB Output is correct
5 Correct 731 ms 22252 KB Output is correct
6 Correct 507 ms 22248 KB Output is correct
7 Correct 707 ms 20844 KB Output is correct
8 Correct 233 ms 26596 KB Output is correct
9 Correct 195 ms 18404 KB Output is correct