Submission #102313

#	Time	Username	Problem	Language	Result	Execution time	Memory
102313		rubenvd	Ball Machine (BOI13_ballmachine)	C++11	40.71 / 100	1084 ms	11436 KiB

ballmachine

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

bool compareInt(const int& lhs, const int& rhs)
{
  return val[lhs] < val[rhs];
}

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

pair<int, int> add( int u, int cnt ){
	//cout << u << " " << cnt << endl;
	bool used = false;
	pair<int, int> ret;
	for( auto v : child[u] ){
		used = true;
		if( !filled[v] && cnt > 0 ){
			ret = add(v, cnt);
			cnt = ret.second;
		}
	}


	if( !used || cnt > 0 ){
		filled[u] = true;
		return {u, cnt-1};
	}
	else{
		return {ret.first, cnt};
	}
}

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

	while( filled[in] ){
		prev = par[prev];
		cnt++;
		in = par[in];
	}

	filled[prev] = false;
	return cnt;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	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;
	}

	dfs(root);
	for( int i = 0; i < n; ++i )
		sort(child[i].begin(), child[i].end(), compareInt);

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

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:79:13: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
    out = add(root, k);
          ~~~^~~~~~~~~

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