oj.uz

Submission #282996

# Submission time Handle Problem Language Result Execution time Memory
282996 2020-08-25T08:27:56 Z theStaticMind Ball Machine (BOI13_ballmachine) C++14
100 / 100
 870 ms 38548 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

vector<int> adj[100005];
vector<int> sub(100005, INF);
int anc[20][100005];
int T[100005];
int d[100005];
int root = 0;
map<int, int> emp;

void init(int x){
	sub[x] = x;
	for(auto y : adj[x]) init(y), sub[x] = min(sub[x], sub[y]);
	sort(all(adj[x]), [&](int x, int y){return sub[x] < sub[y];});
}

void dfs(int x){
	static int time = 1;
	for(auto y : adj[x]){
		d[y] = d[x] + 1;
		dfs(y);
	}
	T[x] = time++;
	emp[T[x]] = x;
}

int add(int k){
	int ret;
	while(k--){
		ret = emp.begin()->second;
		emp.erase(emp.begin());
	}
	return ret;
}

int erase(int x){
	assert(!emp.count(T[x]));

	int y = x;

	for(int d = 19; d >= 0; d--){
		if(!emp.count(T[anc[d][y]])) y = anc[d][y];
	}

	assert(y);

	emp[T[y]] = y;

	return d[x] - d[y]; 

}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, q;
	cin >> n >> q;

	for(int i = 1; i <= n; i++){
		int x;
		cin >> x;
		adj[x].pb(i);
		anc[0][i] = x;
		if(!x) root = i;
	}

	for(int d = 1; d < 20; d++){
		for(int x = 1; x <= n; x++) anc[d][x] = anc[d - 1][anc[d - 1][x]];
	}
	
	init(root);
	dfs(0);

	while(q--){
		int k, x;
		cin >> k >> x;

		if(k == 1){
			cout << add(x) << "\n";
		}
		else{
			cout << erase(x) << "\n";
		}
	}
}

Compilation message

ballmachine.cpp: In function 'long long int add(long long int)':
ballmachine.cpp:42:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |  return ret;
      |         ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3712 KB Output is correct
2 Correct 551 ms 21224 KB Output is correct
3 Correct 213 ms 21368 KB Output is correct
4 Correct 3 ms 3584 KB Output is correct
5 Correct 3 ms 3712 KB Output is correct
6 Correct 4 ms 3840 KB Output is correct
7 Correct 4 ms 3840 KB Output is correct
8 Correct 4 ms 3840 KB Output is correct
9 Correct 17 ms 4736 KB Output is correct
10 Correct 64 ms 7936 KB Output is correct
11 Correct 526 ms 21340 KB Output is correct
12 Correct 214 ms 21368 KB Output is correct
13 Correct 453 ms 21240 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 10416 KB Output is correct
2 Correct 808 ms 33612 KB Output is correct
3 Correct 200 ms 29680 KB Output is correct
4 Correct 315 ms 13648 KB Output is correct
5 Correct 369 ms 13048 KB Output is correct
6 Correct 395 ms 13176 KB Output is correct
7 Correct 360 ms 12024 KB Output is correct
8 Correct 100 ms 10360 KB Output is correct
9 Correct 632 ms 33788 KB Output is correct
10 Correct 791 ms 33400 KB Output is correct
11 Correct 605 ms 33404 KB Output is correct
12 Correct 730 ms 31224 KB Output is correct
13 Correct 196 ms 34040 KB Output is correct
14 Correct 206 ms 29752 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 18936 KB Output is correct
2 Correct 730 ms 32376 KB Output is correct
3 Correct 428 ms 31096 KB Output is correct
4 Correct 371 ms 28152 KB Output is correct
5 Correct 530 ms 27804 KB Output is correct
6 Correct 579 ms 27644 KB Output is correct
7 Correct 572 ms 26360 KB Output is correct
8 Correct 452 ms 31224 KB Output is correct
9 Correct 602 ms 34296 KB Output is correct
10 Correct 870 ms 34212 KB Output is correct
11 Correct 780 ms 33924 KB Output is correct
12 Correct 840 ms 32352 KB Output is correct
13 Correct 744 ms 38548 KB Output is correct
14 Correct 467 ms 30064 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 34424 KB Output is correct
2 Correct 779 ms 32304 KB Output is correct
3 Correct 206 ms 37896 KB Output is correct
4 Correct 641 ms 34436 KB Output is correct
5 Correct 831 ms 33900 KB Output is correct
6 Correct 606 ms 34008 KB Output is correct
7 Correct 843 ms 32444 KB Output is correct
8 Correct 207 ms 37884 KB Output is correct
9 Correct 222 ms 29680 KB Output is correct