oj.uz

Submission #81576

# Submission time Handle Problem Language Result Execution time Memory
81576 2018-10-25T11:44:46 Z arman_ferdous Ball Machine (BOI13_ballmachine) C++17
100 / 100
 328 ms 74384 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
const int N = 1e5+10;

int n, q, p[N][18], root, sub[N], lev[N], idx[N];
vector<int> g[N];
deque<int> eul;

int dfs(int u, int f, int l) {
	sub[u] = u;
	lev[u] = l;
	for(int v : g[u]) if(v != f)
		sub[u] = min(sub[u], dfs(v,u,l+1));
	return sub[u];
}

void flat(int u, int f) {
	vector<ii> tmp;
	for(int v : g[u]) if(v != f)
		tmp.push_back({sub[v],v});
	sort(tmp.begin(),tmp.end());
	for(auto v : tmp) 
		flat(v.second,u);
	eul.push_back(u);
}

struct segtree {
	int t[N<<2], stat[N];
	void build(int node, int L, int R) {
		if(L == R)  return void(t[node] = stat[L] = 1);
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		build(lc,L,mid), build(rc,mid+1,R);
		t[node] = t[lc] + t[rc];
	}
	bool check(int pos) { return stat[pos]; }
	void on(int node, int L, int R, int pos) {
		if(L == R)  return void(t[node] = stat[L] = 1);
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		pos <= mid ? on(lc,L,mid,pos) : on(rc,mid+1,R,pos);
		t[node] = t[lc] + t[rc];
	}
	void off(int node, int L, int R, int pos) {
		if(L == R)  return void(t[node] = stat[L] = 0);
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		pos <= mid ? off(lc,L,mid,pos) : off(rc,mid+1,R,pos);
		t[node] = t[lc] + t[rc];
	}
	int kth(int node, int L, int R, int k) {
		if(L == R) return L;
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		if(k <= t[lc]) return kth(lc,L,mid,k);
		return kth(rc,mid+1,R,k-t[lc]);
	}
}ds;

int main() {
	memset(p,-1,sizeof p);
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; i++) {
		int v;
		scanf("%d", &v);
		if(v) g[i].push_back(v), g[v].push_back(i), p[i][0] = v;
		if(!v) root = i;
	}
	for(int j = 1; j < 18; j++) 
		for(int i = 1; i <= n; i++)
			if(p[i][j-1] != -1)
				p[i][j] = p[p[i][j-1]][j-1];
	dfs(root,-1,0);
	flat(root,-1);

	/*for(int i = 0; i < n; i++)
		cout << eul[i] << " ";
	cout << endl;*/

	for(int i = 0; i < n; i++)
		idx[eul[i]] = i;

	ds.build(1,0,n-1);
	while(q--) {
		int t, x;
		scanf("%d %d", &t, &x);
		if(t == 1) {
			int idx;
			while(x--) {
				idx = ds.kth(1,0,n-1,1);
				//cout << "goes to " << eul[idx] << endl;
				ds.off(1,0,n-1,idx);
			}
			printf("%d\n", eul[idx]);
		}
		else {
			int u = x;
			for(int i = 17; i >= 0; i--) {
				if(p[u][i] != -1 && ds.check(idx[p[u][i]]) == 0)
					u = p[u][i];
			}
			//cout << "biggest on parent = " << u << endl;
			ds.on(1,0,n-1,idx[u]);
			printf("%d\n", lev[x] - lev[u]);
		}
		//for(int i = 0; i < n; i++) 
			//cout << eul[i] << " " << ds.check(i-1) << endl;
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:60: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:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v);
   ~~~~~^~~~~~~~~~
ballmachine.cpp:84:8: 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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 152 ms 15108 KB Output is correct
3 Correct 98 ms 16216 KB Output is correct
4 Correct 10 ms 16216 KB Output is correct
5 Correct 12 ms 16216 KB Output is correct
6 Correct 11 ms 16216 KB Output is correct
7 Correct 10 ms 16216 KB Output is correct
8 Correct 11 ms 16216 KB Output is correct
9 Correct 17 ms 16216 KB Output is correct
10 Correct 40 ms 16216 KB Output is correct
11 Correct 140 ms 17740 KB Output is correct
12 Correct 103 ms 18768 KB Output is correct
13 Correct 163 ms 19728 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 19844 KB Output is correct
2 Correct 257 ms 29916 KB Output is correct
3 Correct 134 ms 29916 KB Output is correct
4 Correct 97 ms 29916 KB Output is correct
5 Correct 113 ms 29916 KB Output is correct
6 Correct 104 ms 29916 KB Output is correct
7 Correct 99 ms 29916 KB Output is correct
8 Correct 59 ms 29916 KB Output is correct
9 Correct 236 ms 35676 KB Output is correct
10 Correct 273 ms 37080 KB Output is correct
11 Correct 228 ms 38612 KB Output is correct
12 Correct 254 ms 38612 KB Output is correct
13 Correct 180 ms 45276 KB Output is correct
14 Correct 123 ms 45276 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 45276 KB Output is correct
2 Correct 275 ms 45276 KB Output is correct
3 Correct 191 ms 47604 KB Output is correct
4 Correct 171 ms 47604 KB Output is correct
5 Correct 241 ms 47604 KB Output is correct
6 Correct 201 ms 47604 KB Output is correct
7 Correct 180 ms 47604 KB Output is correct
8 Correct 204 ms 52288 KB Output is correct
9 Correct 241 ms 52288 KB Output is correct
10 Correct 293 ms 52344 KB Output is correct
11 Correct 284 ms 53820 KB Output is correct
12 Correct 276 ms 53820 KB Output is correct
13 Correct 273 ms 62820 KB Output is correct
14 Correct 174 ms 62820 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 62820 KB Output is correct
2 Correct 272 ms 62820 KB Output is correct
3 Correct 215 ms 67744 KB Output is correct
4 Correct 328 ms 67744 KB Output is correct
5 Correct 295 ms 67744 KB Output is correct
6 Correct 246 ms 67744 KB Output is correct
7 Correct 297 ms 67744 KB Output is correct
8 Correct 277 ms 74384 KB Output is correct
9 Correct 147 ms 74384 KB Output is correct