Submission #102199

#	Time	Username	Problem	Language	Result	Execution time	Memory
102199		rubenvd	Ball Machine (BOI13_ballmachine)	C++14	1.92 / 100	1084 ms	11456 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
int par[100005], val[100005];
bool filled[100005];
vector<int> child[100005];


int dfs( int u ){
	int mini = 1e9;
	for( auto v : child[u] ){
		mini = min(dfs(v), mini);
	}
	val[u] = min(u, mini);
	
	if( mini != 1e9 )
		return mini;
	else
		return u;
}

int add( int u ){
	int in, mini = 1e9;
	for( auto v : child[u] ){
		if( val[v] < mini && !filled[v] ){
			in = v;
			mini = val[v];
		}
	}


	if( mini == 1e9 ){
		filled[u] = true;
		return u;
	}
	else
		return add(in);
}

int del( int u ){
	int in = par[u], cnt = 0, prev = u;

	//cout << " " << in << endl;
	while( filled[in] ){
		//cout << " " << in << endl;
		prev = par[prev];
		cnt++;
		in = par[in];
	}

	filled[prev] = false;
	return cnt;
}

int main(){
	int n, q, root, type, k;
	cin >> n >> q;
	memset(filled, false, sizeof filled);

	for( int i = 1; i <= n; ++i ){
		cin >> par[i];
		child[par[i]].push_back(i);
		if( par[i] == 0 )
			root = i;
	}
	child[0].push_back(root);
	par[root]=0;

	dfs(root);

	for( int i= 0; i < q; ++i ){
		cin >> type >> k;
		if( type == 1 ){
			int out;
			for( int i = 0; i < k; ++i ){
				out = add(root);
			}
			cout << out << endl;
		} else {
			cout << del(k) << endl;
		}
	}
	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int add(int)':
ballmachine.cpp:32:13: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
   filled[u] = true;
   ~~~~~~~~~~^~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:32:13: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
   filled[u] = true;
   ~~~~~~~~~~^~~~~~
ballmachine.cpp:22:6: note: 'in' was declared here
  int in, mini = 1e9;
      ^~

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