Submission #398723

#	Time	Username	Problem	Language	Result	Execution time	Memory
398723		nafis_shifat	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	443 ms	28096 KiB

ballmachine

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
vector<int> adj[mxn];
int dp[mxn][20];
int level[mxn];
int mn[mxn];
int out[mxn];
int tn[mxn];
int T = 0;
bool on[mxn] = {};

set<int> st;
void dfs1(int cur) {
	mn[cur] = cur;
	for(int u : adj[cur]) {
		level[u] = level[cur] + 1;
		dfs1(u);
		mn[cur] = min(mn[cur],mn[u]);
	}
}

void dfs(int cur) {

	for(int i = 1; i < 20; i++) dp[cur][i] = dp[dp[cur][i - 1]][i - 1];
	for(int u : adj[cur]) {
		dfs(u);
	}
	T++;
	out[cur] = T;
	tn[T] = cur;
	st.insert(T);
}

int dlt(int u) {
	for(int i = 19; i >= 0; i--) {
		if(on[dp[u][i]]) {
			u = dp[u][i];
		}
	}
	on[u] = false;
	st.insert(out[u]);
	return level[u];

}
int main() {
	int n,q;
	cin >> n >> q;
	int root;
	for(int i = 1; i <= n; i++) {
		cin >> dp[i][0];
		if(!dp[i][0]) root = i;
		adj[dp[i][0]].push_back(i); 
	}
	level[root] = 1;
	dfs1(root);
	for(int i = 1; i <= n; i++) {
		sort(adj[i].begin(),adj[i].end(),[](int a,int b) {
			return mn[a] < mn[b];
		});
	}

	dfs(root);

	while(q--) {
		int a,b;
		cin >> a >> b;
		if(a == 1) {
			int ans;
			for(int i = 1; i <= b; i++) {
				int x = *st.begin();
				on[tn[x]] = true;
				ans = tn[x];
				st.erase(x);
			}
			cout<<ans<<endl;

		} else {
			cout<<level[b] - dlt(b)<<endl;
		}
	} 



	
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:79:10: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |    cout<<ans<<endl;
      |          ^~~
ballmachine.cpp:66:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |  dfs(root);
      |  ~~~^~~~~~

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