oj.uz

Submission #298036

# Submission time Handle Problem Language Result Execution time Memory
298036 2020-09-12T10:04:20 Z miss_robot Ball Machine (BOI13_ballmachine) C++14
100 / 100
 370 ms 26344 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
using namespace std;
 
const int N = 100000, L = 17;
int n, q, k, root, temp, c;
int p[L][N], mi[N], ball[N], lv[N], num[N];
vector<int> g[N];

bool comp(const int &a, const int &b){
	return mi[a] < mi[b];
}

void dfs(int u, int h){
	mi[u] = u;
	lv[u] = h++;
	for(int v : g[u]) dfs(v, h), mi[u] = min(mi[u], mi[v]);
	sort(g[u].begin(), g[u].end(), comp);
}

void traverse(int u){
	for(int v : g[u]) traverse(v);
	num[u] = c++;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin >> n >> q;
	for(int i = 0, j; i < n; i++){
		cin >> j;
		if(!j) root = i, p[0][i] = i;
		else j--, p[0][i] = j, g[j].push_back(i);
	}
	dfs(root, 0);
	traverse(root);
	priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
	for(int i = 0; i < n; i++) pq.push({num[i], i});
	for(int i = 1; i < L; i++)
		for(int j = 0; j < n; j++)
			p[i][j] = p[i-1][p[i-1][j]];
	while(q--){
		cin >> temp >> k;
		if(--temp){
			k--;
			temp = k;
			for(int i = L-1; i >= 0; i--)
				if(ball[p[i][k]]) k = p[i][k];
			ball[k] = 0;
			pq.push({num[k], k});
			cout << lv[temp] - lv[k] << "\n";
		}
		else{
			while(k--){
				if(!k) cout << pq.top().second+1 << "\n";
				ball[pq.top().second] = 1;
				pq.pop();
			}
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 234 ms 11120 KB Output is correct
3 Correct 70 ms 10992 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2944 KB Output is correct
7 Correct 3 ms 2944 KB Output is correct
8 Correct 4 ms 2944 KB Output is correct
9 Correct 9 ms 3328 KB Output is correct
10 Correct 25 ms 4864 KB Output is correct
11 Correct 245 ms 11120 KB Output is correct
12 Correct 69 ms 10992 KB Output is correct
13 Correct 185 ms 11248 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7540 KB Output is correct
2 Correct 366 ms 20080 KB Output is correct
3 Correct 82 ms 14064 KB Output is correct
4 Correct 93 ms 8692 KB Output is correct
5 Correct 103 ms 8500 KB Output is correct
6 Correct 91 ms 8564 KB Output is correct
7 Correct 86 ms 7544 KB Output is correct
8 Correct 38 ms 7604 KB Output is correct
9 Correct 354 ms 20464 KB Output is correct
10 Correct 370 ms 20208 KB Output is correct
11 Correct 247 ms 20076 KB Output is correct
12 Correct 353 ms 17384 KB Output is correct
13 Correct 129 ms 23148 KB Output is correct
14 Correct 82 ms 14220 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 11764 KB Output is correct
2 Correct 345 ms 17904 KB Output is correct
3 Correct 209 ms 21360 KB Output is correct
4 Correct 218 ms 17000 KB Output is correct
5 Correct 208 ms 16620 KB Output is correct
6 Correct 214 ms 16624 KB Output is correct
7 Correct 198 ms 14832 KB Output is correct
8 Correct 214 ms 21356 KB Output is correct
9 Correct 365 ms 20716 KB Output is correct
10 Correct 359 ms 20208 KB Output is correct
11 Correct 358 ms 20460 KB Output is correct
12 Correct 341 ms 17808 KB Output is correct
13 Correct 360 ms 26344 KB Output is correct
14 Correct 289 ms 14956 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 20848 KB Output is correct
2 Correct 347 ms 17772 KB Output is correct
3 Correct 151 ms 25560 KB Output is correct
4 Correct 345 ms 20700 KB Output is correct
5 Correct 367 ms 20204 KB Output is correct
6 Correct 232 ms 20260 KB Output is correct
7 Correct 361 ms 17900 KB Output is correct
8 Correct 133 ms 25584 KB Output is correct
9 Correct 80 ms 14064 KB Output is correct