Submission #36405

#	Time	Username	Problem	Language	Result	Execution time	Memory
36405		ToMoClone	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	299 ms	22528 KiB

ballmachine

/*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 (stderr)

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 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5