Submission #102534

#	Time	Username	Problem	Language	Result	Execution time	Memory
102534		rubenvd	Ball Machine (BOI13_ballmachine)	C++14	55.79 / 100	1090 ms	14316 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
int par[100005], val[100005], num = 0, numD = 0, place[100005];
bool filled[100005];
vector<int> child[100005], topo;
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 ){
	int mini = 1e9;
	for( auto v : child[u] ){
		mini = min(dfs(v), mini);
	}

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

	val[u] = min(u, mini);
	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 in = par[u], cnt = 0, prev = u;

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

	deleted.push(place[prev]);
	filled[prev] = false;
	return cnt;
}

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];
		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);
	topo.clear();
	dfs(root);
	for( int i = 0; i < topo.size(); ++i )
		deleted.push(place[topo[i]]);

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

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:71: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:34:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return last;
         ^~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:70:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(root);
  ~~~^~~~~~

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