Submission #81576

#	Time	Username	Problem	Language	Result	Execution time	Memory
81576		arman_ferdous	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	328 ms	74384 KiB

ballmachine

#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 (stderr)

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