Submission #26658

#	Time	Username	Problem	Language	Result	Execution time	Memory
26658		kdh9949	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	299 ms	33208 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

struct Nod{
	int p, x;
	bool operator<(const Nod &oth) const {
		return p > oth.p;
	}
};

priority_queue<Nod> pq;
int n, q, r, mn[100010], pn[100010], cnt, c[100010], sp[17][100010];
vector<int> ch[100010], nc[100010];

int g(int x){
	priority_queue<Nod> pq;
	for(auto &i : ch[x]){
		pq.push({g(i), i});
	}
	int ret = x;
	for(; !pq.empty(); pq.pop()){
		nc[x].push_back(pq.top().x);
		ret = min(ret, pq.top().p);
	}
	return ret;
}

void f(int x){
	for(int i = 1; i < 17; i++) sp[i][x] = sp[i - 1][sp[i - 1][x]];
	for(auto &i : nc[x]) f(i);
	pn[x] = ++cnt;
	pq.push({pn[x], x});
}

int main(){
	scanf("%d%d", &n, &q);
	for(int i = 1; i <= n; i++){
		scanf("%d", sp[0] + i);
		if(!sp[0][i]) r = i;
		else ch[sp[0][i]].push_back(i);
	}
	g(r);
	f(r);
	for(int t, x, ans; q--; ){
		scanf("%d%d", &t, &x);
		if(t == 1){
			while(x--){
				ans = pq.top().x;
				c[pq.top().x] = 1;
				pq.pop();
			}
			printf("%d\n", ans);
		}
		else{
			ans = 0;
			for(int i = 16; i >= 0; i--){
				if(c[sp[i][x]]){
					ans += (1 << i);
					x = sp[i][x];
				}
			}
			c[x] = 0;
			pq.push({pn[x], x});
			printf("%d\n", ans);
		}
	}
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:36: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:38:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", sp[0] + i);
                         ^
ballmachine.cpp:45:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &t, &x);
                        ^

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5