oj.uz

Submission #54160

# Submission time Handle Problem Language Result Execution time Memory
54160 2018-07-02T14:07:57 Z Bruteforceman Ball Machine (BOI13_ballmachine) C++11
100 / 100
 323 ms 69952 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2808 KB Output is correct
2 Correct 137 ms 12272 KB Output is correct
3 Correct 128 ms 13024 KB Output is correct
4 Correct 4 ms 13024 KB Output is correct
5 Correct 4 ms 13024 KB Output is correct
6 Correct 5 ms 13024 KB Output is correct
7 Correct 8 ms 13024 KB Output is correct
8 Correct 6 ms 13024 KB Output is correct
9 Correct 16 ms 13024 KB Output is correct
10 Correct 51 ms 13024 KB Output is correct
11 Correct 188 ms 15004 KB Output is correct
12 Correct 78 ms 15632 KB Output is correct
13 Correct 147 ms 16592 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16592 KB Output is correct
2 Correct 196 ms 27348 KB Output is correct
3 Correct 111 ms 27348 KB Output is correct
4 Correct 98 ms 27348 KB Output is correct
5 Correct 102 ms 27348 KB Output is correct
6 Correct 88 ms 27348 KB Output is correct
7 Correct 94 ms 27348 KB Output is correct
8 Correct 44 ms 27348 KB Output is correct
9 Correct 193 ms 33664 KB Output is correct
10 Correct 187 ms 34764 KB Output is correct
11 Correct 177 ms 35292 KB Output is correct
12 Correct 177 ms 35292 KB Output is correct
13 Correct 113 ms 40644 KB Output is correct
14 Correct 92 ms 40644 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 40644 KB Output is correct
2 Correct 204 ms 40644 KB Output is correct
3 Correct 136 ms 43620 KB Output is correct
4 Correct 196 ms 43620 KB Output is correct
5 Correct 119 ms 43620 KB Output is correct
6 Correct 184 ms 43620 KB Output is correct
7 Correct 122 ms 43620 KB Output is correct
8 Correct 161 ms 48284 KB Output is correct
9 Correct 289 ms 49356 KB Output is correct
10 Correct 186 ms 50376 KB Output is correct
11 Correct 211 ms 51832 KB Output is correct
12 Correct 228 ms 51832 KB Output is correct
13 Correct 323 ms 59840 KB Output is correct
14 Correct 208 ms 59840 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 59840 KB Output is correct
2 Correct 184 ms 59840 KB Output is correct
3 Correct 128 ms 63432 KB Output is correct
4 Correct 224 ms 63432 KB Output is correct
5 Correct 215 ms 63432 KB Output is correct
6 Correct 161 ms 63432 KB Output is correct
7 Correct 271 ms 63432 KB Output is correct
8 Correct 128 ms 69952 KB Output is correct
9 Correct 95 ms 69952 KB Output is correct