Submission #54160

#	Time	Username	Problem	Language	Result	Execution time	Memory
54160		Bruteforceman	Ball Machine (BOI13_ballmachine)	C++11	100 / 100	323 ms	69952 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
int sub[100010];
vector <int> g[100010];
int pos[100010];
int node[100010];
int cur;
int tym;
int n;

int l[100010], r[100010];
int dp[20][100010];
int dep[100010];
const int logn = 19;

bool cmp(int p, int q) {
	return sub[p] < sub[q];
}
void dfs(int x) {
	sub[x] = x;
	for(int i : g[x]) {
		dp[0][i] = x;
		dfs(i);
		sub[x] = min(sub[x], sub[i]);
	}
	sort(g[x].begin(), g[x].end(), cmp);	
}
void order(int x) {
	l[x] = ++tym;
	for(auto i : g[x]) {
		order(i);
	}
	pos[x] = ++cur;
	node[cur] = x;
	r[x] = tym;
}

int t[100010 * 4];
void update(int x, int val, int c = 1, int b = 1, int e = n) {
	if(b == e) {
		t[c] = val;
		return ;
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(x <= m) {
		update(x, val, l, b, m);
	} else {
		update(x, val, r, m+1, e);
	}
	t[c] = min(t[l], t[r]);
}
int get(int c = 1, int b = 1, int e = n) {
	if(b == e) {
		return node[b];
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(t[l] == 0) return get(l, b, m);
	else return get(r, m+1, e);
}



int bit[100010];
void upd(int x, int val) {
	for(int i = x; i <= n; i += i & (-i)) {
		bit[i] += val;
	}
}
int query(int x) {
	int ans = 0;
	for(int i = x; i > 0; i -= i & (-i)) {
		ans += bit[i];
	}
	return ans;
} 
int lift(int x, int up) {
	for(int i = logn; i >= 0; i--) {
		if((1 << i) <= up) {
			x = dp[i][x];
			up -= 1 << i;
		}
	}
	return x;
}

int main() {
	int q;
	scanf("%d %d", &n, &q);
	int root = 1;
	for(int i = 1; i <= n; i++) {
		int p;
		scanf("%d", &p);
		g[p].emplace_back(i);
		if(p == 0) {
			root = i;
		}
	}	
	dfs(root);
	order(root);
	for(int i = 1; i <= logn; i++) {
		for(int j = 1; j <= n; j++) {
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
		}
	}
	for(int i = 0; i < q; i++) {
		int c, x;
		scanf("%d %d", &c, &x);
		if(c == 1) {
			int y = -1;
			for(int j = 0; j < x; j++) {
				y = get();
				update(pos[y], 1);
				upd(l[y], 1);
				upd(r[y] + 1, -1);
			}
			printf("%d\n", y);
		} else {
			int cnt_on = query(l[x]);
			int y = lift(x, cnt_on - 1);
			upd(l[y], -1);
			upd(r[y] + 1, 1);
			update(pos[y], 0);
			printf("%d\n", cnt_on - 1);
		}
	}
	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p);
   ~~~~~^~~~~~~~~~
ballmachine.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &c, &x);
   ~~~~~^~~~~~~~~~~~~~~~~

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