Submission #535485

#	Time	Username	Problem	Language	Result	Execution time	Memory
535485		faik	Ball Machine (BOI13_ballmachine)	C++14	0 / 100	1098 ms	37564 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

#define MOD 998244353
#define INF 1000000001
#define LNF 1000000000000000001

#define int ll

typedef long long ll;
typedef pair<int,int> pii;

int dfsmin(int x,int last,vector<vector<int> > &edges,vector<int> &mn, vector<int> &height){
	int ret = x;
	if(last == x)
		height[x] = 0;
	else
		height[x] = height[last]+1;
	for(int i : edges[x]){
		if(i != last){
			ret = min(ret,dfsmin(i,x,edges,mn,height));
		}
	}
	sort(edges[x].begin(), edges[x].end(),[&mn](int a,int b){return mn[a] < mn[b];});
	mn[x] = ret;
	return ret;
}

void dfssec(int x,int last,vector<vector<int> > &edges, vector<int> &sec){
	static int counter = 0;
	for(int i : edges[x]){
		if(i != last){
			dfssec(i,x,edges,sec);
		}
	}
	sec[counter++] = x;
}
int l;

int lg(int x){
	int cnt = 0;
	while(x){x>>=1;cnt++;}
	return cnt;
}

void solve(){
//#define TEST
	int n,q;cin >> n >> q;
	vector<vector<int> > edges(n);
	vector<int> parent(n);
	for(int i = 0;i < n;i++){
		int p;cin >> p;p--;
		if(p != -1){
			edges[i].push_back(p);
			edges[p].push_back(i);
			parent[i] = p;
		}
	}

	vector<int> height(n);
	vector<int> mn(n);
	dfsmin(0,0,edges,mn,height);
	
	vector<int> sec(n);
	dfssec(0,0,edges,sec);
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	for(int i = 0;i < n;i++){
		pq.push({sec[i],i});
	}

	l = lg(n);
	vector<vector<int> > up(n);
	up.assign(n,vector<int>(l+1,0));
	for(int i = 0;i < n;i++)
		up[i][0] = parent[i];

	for(int i = 1;i <= l;i++){
		for(int j = 0;j < n;j++){
			up[j][i] = up[up[j][i-1]][i-1];
		}
	}
	vector<int> filled(n);
	for(int t = 0;t < q;t++){
		int i,x;cin >> i >> x;
		if(i == 1){
			int last;
			for(int j = 0;j < x;j++){
				last = pq.top().second;
				pq.pop();
				filled[last] = true;
			}
			cout << last << '\n';
		} else if(i == 2){
			x--;
			int next = x;
			for(int j = l;j >= 0;j--){
				while(filled[up[next][j]] && next != 0){
					next = up[next][j];
				}
			}
			filled[next] = false;
			pq.push({sec[next],next});
			cout << height[x]-height[next] << '\n';
		}
	}
}

signed main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
#ifdef DEBUG
	freopen("i.txt","r",stdin);
	freopen("o.txt","w",stdout);
#endif
	int t = 1;
#ifdef TEST
	cin >> t;
#endif
	while(t--){
		solve();
	}

	return 0;
}

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