oj.uz

Submission #36405

# Submission time Handle Problem Language Result Execution time Memory
36405 2017-12-08T16:55:00 Z ToMoClone Ball Machine (BOI13_ballmachine) C++14
100 / 100
 299 ms 22528 KB 
/*input
*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

const int N = 100001;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Empty;
vector<int> child[N];
int n, q, cnt, Min[N], par[17][N], Ball[N], Pos[N];

void dfs(int u){
	for(int v:child[u])
		dfs(v), Min[u] = min(Min[u], Min[v]);

	sort(child[u].begin(), child[u].end(), [&](int a, int b){
		return Min[a] < Min[b];
	});
}

void dfs2(int u){
	for(int v:child[u]) dfs2(v);
	Empty.push(make_pair(Pos[u] = ++cnt, u));
}

int main(){
	scanf("%d%d", &n, &q);
	for(int i = 1; i <= n; ++i){
		int u; scanf("%d", &u);
		child[u].push_back(i);
		par[0][i] = u, Min[i] = i;
	}
	for(int i = 1; i <= n; ++i)
		if(par[0][i] == 0) dfs(i);
	for(int i = 1; i <= n; ++i)
		if(par[0][i] == 0) dfs2(i);

	for(int j = 1; j < 17; ++j)
		for(int i = 1; i <= n; ++i)
			par[j][i] = par[j - 1][par[j - 1][i]];

	while(q--){
		int type; scanf("%d", &type);
		if(type == 2){
			int u, jump = 0; scanf("%d", &u);
			for(int i = 16; i >= 0; --i)
				if(Ball[par[i][u]]) u = par[i][u], jump += (1 << i);
			printf("%d\n", jump);

			Ball[u] = 0, Empty.push(make_pair(Pos[u], u));
		}
		else {
			int num, LastNode = 0; scanf("%d", &num);
			while(num--){
				LastNode = Empty.top().second, Empty.pop();
				Ball[LastNode] = 1;
			}
			printf("%d\n", LastNode);
		}
	}
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:27:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
                       ^
ballmachine.cpp:29:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u; scanf("%d", &u);
                         ^
ballmachine.cpp:43:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int type; scanf("%d", &type);
                               ^
ballmachine.cpp:45:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int u, jump = 0; scanf("%d", &u);
                                    ^
ballmachine.cpp:53:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int num, LastNode = 0; scanf("%d", &num);
                                            ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12180 KB Output is correct
2 Correct 173 ms 14056 KB Output is correct
3 Correct 79 ms 14056 KB Output is correct
4 Correct 0 ms 12180 KB Output is correct
5 Correct 0 ms 12180 KB Output is correct
6 Correct 0 ms 12180 KB Output is correct
7 Correct 0 ms 12180 KB Output is correct
8 Correct 3 ms 12180 KB Output is correct
9 Correct 9 ms 12312 KB Output is correct
10 Correct 29 ms 12708 KB Output is correct
11 Correct 166 ms 14056 KB Output is correct
12 Correct 113 ms 14056 KB Output is correct
13 Correct 123 ms 14056 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 14140 KB Output is correct
2 Correct 203 ms 18488 KB Output is correct
3 Correct 119 ms 15356 KB Output is correct
4 Correct 99 ms 14096 KB Output is correct
5 Correct 93 ms 13964 KB Output is correct
6 Correct 89 ms 13964 KB Output is correct
7 Correct 96 ms 13460 KB Output is correct
8 Correct 53 ms 14144 KB Output is correct
9 Correct 236 ms 18908 KB Output is correct
10 Correct 236 ms 18488 KB Output is correct
11 Correct 206 ms 18488 KB Output is correct
12 Correct 196 ms 16980 KB Output is correct
13 Correct 153 ms 21492 KB Output is correct
14 Correct 103 ms 15356 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 15524 KB Output is correct
2 Correct 226 ms 17060 KB Output is correct
3 Correct 159 ms 20756 KB Output is correct
4 Correct 119 ms 17864 KB Output is correct
5 Correct 123 ms 17528 KB Output is correct
6 Correct 139 ms 17536 KB Output is correct
7 Correct 113 ms 16392 KB Output is correct
8 Correct 153 ms 20760 KB Output is correct
9 Correct 193 ms 18916 KB Output is correct
10 Correct 243 ms 18492 KB Output is correct
11 Correct 256 ms 18500 KB Output is correct
12 Correct 266 ms 17064 KB Output is correct
13 Correct 299 ms 22528 KB Output is correct
14 Correct 163 ms 15360 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 18908 KB Output is correct
2 Correct 229 ms 17060 KB Output is correct
3 Correct 179 ms 22524 KB Output is correct
4 Correct 246 ms 18912 KB Output is correct
5 Correct 176 ms 18492 KB Output is correct
6 Correct 186 ms 18500 KB Output is correct
7 Correct 206 ms 17060 KB Output is correct
8 Correct 166 ms 22524 KB Output is correct
9 Correct 123 ms 15360 KB Output is correct