oj.uz

Submission #102358

# Submission time Handle Problem Language Result Execution time Memory
102358 2019-03-24T13:32:03 Z rubenvd Ball Machine (BOI13_ballmachine) C++11
0 / 100
 145 ms 12872 KB 
#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();
	}

	for( num; cnt > 0 && num < topo.size(); cnt-- ){
		last = topo[num];
		filled[topo[num]] = true;
		num++;
	}
	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 < q; ++i ){
		cin >> type >> k;
		if( type == 1 ){
			int out = add(k);
			cout << out << "\n";
		} else {
			cout << /*del(k)*/ 0 << "\n";
		}
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'int add(int)':
ballmachine.cpp:34:10: warning: statement has no effect [-Wunused-value]
  for( num; cnt > 0 && num < topo.size(); cnt-- ){
          ^
ballmachine.cpp:34:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for( num; cnt > 0 && num < topo.size(); cnt-- ){
                       ~~~~^~~~~~~~~~~~~
ballmachine.cpp:39:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return last;
         ^~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:75:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(root);
  ~~~^~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2688 KB Output isn't correct
2 Incorrect 47 ms 5364 KB Output isn't correct
3 Incorrect 78 ms 5364 KB Output isn't correct
4 Incorrect 5 ms 2688 KB Output isn't correct
5 Incorrect 5 ms 2688 KB Output isn't correct
6 Incorrect 6 ms 2864 KB Output isn't correct
7 Incorrect 5 ms 2688 KB Output isn't correct
8 Incorrect 5 ms 2688 KB Output isn't correct
9 Incorrect 11 ms 2816 KB Output isn't correct
10 Incorrect 14 ms 3328 KB Output isn't correct
11 Incorrect 64 ms 5236 KB Output isn't correct
12 Incorrect 75 ms 5272 KB Output isn't correct
13 Incorrect 63 ms 5108 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 4728 KB Output isn't correct
2 Incorrect 120 ms 9076 KB Output isn't correct
3 Incorrect 73 ms 6388 KB Output isn't correct
4 Incorrect 37 ms 4992 KB Output isn't correct
5 Incorrect 34 ms 4736 KB Output isn't correct
6 Incorrect 40 ms 4856 KB Output isn't correct
7 Incorrect 36 ms 4352 KB Output isn't correct
8 Incorrect 35 ms 4816 KB Output isn't correct
9 Incorrect 116 ms 9336 KB Output isn't correct
10 Incorrect 101 ms 8948 KB Output isn't correct
11 Incorrect 136 ms 9032 KB Output isn't correct
12 Incorrect 116 ms 7760 KB Output isn't correct
13 Incorrect 140 ms 11608 KB Output isn't correct
14 Incorrect 101 ms 6452 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 6136 KB Output isn't correct
2 Incorrect 118 ms 7924 KB Output isn't correct
3 Incorrect 100 ms 10616 KB Output isn't correct
4 Incorrect 100 ms 8180 KB Output isn't correct
5 Incorrect 96 ms 7800 KB Output isn't correct
6 Incorrect 101 ms 7828 KB Output isn't correct
7 Incorrect 75 ms 6904 KB Output isn't correct
8 Incorrect 105 ms 10616 KB Output isn't correct
9 Incorrect 126 ms 9336 KB Output isn't correct
10 Incorrect 119 ms 8972 KB Output isn't correct
11 Incorrect 136 ms 9032 KB Output isn't correct
12 Incorrect 145 ms 7936 KB Output isn't correct
13 Incorrect 142 ms 12628 KB Output isn't correct
14 Incorrect 109 ms 6256 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 9536 KB Output isn't correct
2 Incorrect 138 ms 7800 KB Output isn't correct
3 Incorrect 121 ms 12656 KB Output isn't correct
4 Incorrect 116 ms 9460 KB Output isn't correct
5 Incorrect 115 ms 8952 KB Output isn't correct
6 Incorrect 104 ms 8952 KB Output isn't correct
7 Incorrect 125 ms 7868 KB Output isn't correct
8 Incorrect 130 ms 12872 KB Output isn't correct
9 Incorrect 81 ms 6376 KB Output isn't correct