Submission #102680

#	Time	Username	Problem	Language	Result	Execution time	Memory
102680		rubenvd	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	271 ms	22352 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
int par[100005][20], val[100005], num = 0, numD = 0, place[100005];
bool filled[100005];
vector<int> child[100005], topo, path;
priority_queue<int, vector<int>, greater<int>> deleted;

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

int dfs( int u ){
	path.push_back(u);
	int mini = 1e9;
	for( auto v : child[u] )
		mini = min(dfs(v), mini);

	place[u] = topo.size();
	topo.push_back(u);

	/*cout << u << endl;
	for( int i = 0; i < path.size(); ++i )
		cout << path[i] << " ";
	cout << endl;*/

	for( int i = 1; i < 17 && (1<<i) < path.size(); i++ )
		par[u][i] = path[path.size() - (1<<i) - 1];

	val[u] = min(u, mini);
	path.pop_back();
	return val[u];
}

int add( int cnt ){
	int last;
	for( ; cnt > 0 && !deleted.empty(); cnt-- ){
		filled[topo[deleted.top()]] = true;
		last = topo[deleted.top()];
		deleted.pop();
	}

	return last;
}

int del( int u ){
	int sum = 0, i = 0;
	//cout << u << " : " << endl;
	while( filled[par[u][i]] == true ){
		//cout << par[u][i] << " " << filled[par[u][i]] << endl;
		i++;
	}

	if( i == 0 ){
		deleted.push(place[u]);
		filled[u] = false;
		return 0;
	} else {
		sum = (1<<(i-1)) + del(par[u][i-1]);
		return sum;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, q, root, type, k;
	cin >> n >> q;

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

	dfs(root);
	for( int i = 1; i <= n; ++i )
		sort(child[i].begin(), child[i].end(), compareInt);
	topo.clear();
	dfs(root);
	for( int i = 0; i < topo.size(); ++i )
		deleted.push(place[topo[i]]);

	/*for( int i = 0; i <= n; ++i ){
		for( int j = 0; j < 5; ++j ){
			cout << par[i][j] << " ";
		}
		cout << endl;
	}*/

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

Compilation message (stderr)

ballmachine.cpp: In function 'int dfs(int)':
ballmachine.cpp:26:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for( int i = 1; i < 17 && (1<<i) < path.size(); i++ )
                            ~~~~~~~^~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for( int i = 0; i < topo.size(); ++i )
                  ~~^~~~~~~~~~~~~
ballmachine.cpp: In function 'int add(int)':
ballmachine.cpp:42:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return last;
         ^~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:82:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(root);
  ~~~^~~~~~

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