oj.uz

Submission #102544

# Submission time Handle Problem Language Result Execution time Memory
102544 2019-03-25T20:05:09 Z rubenvd Ball Machine (BOI13_ballmachine) C++14
60.0794 / 100
 1000 ms 13292 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();
	}

	return last;
}

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

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

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

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 = 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 < q; ++i ){
		cin >> type >> k;
		if( type == 1 ){
			cout << add(k) << "\n";
		} else {
			cout << del(k) << "\n";
		}
	}
	return 0;
}

Compilation message

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 del(int)':
ballmachine.cpp:38:23: warning: 'prev' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int in = u, cnt = 0, prev;
                       ^~~~
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:38:23: warning: 'prev' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int in = u, cnt = 0, prev;
                       ^~~~
ballmachine.cpp:70:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(root);
  ~~~^~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 74 ms 5620 KB Output is correct
3 Correct 66 ms 5892 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 9 ms 2944 KB Output is correct
10 Correct 16 ms 3584 KB Output is correct
11 Correct 97 ms 5552 KB Output is correct
12 Correct 55 ms 5876 KB Output is correct
13 Correct 63 ms 5620 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5112 KB Output is correct
2 Correct 113 ms 9588 KB Output is correct
3 Correct 64 ms 6640 KB Output is correct
4 Correct 43 ms 5240 KB Output is correct
5 Correct 51 ms 5112 KB Output is correct
6 Correct 47 ms 5112 KB Output is correct
7 Correct 51 ms 4600 KB Output is correct
8 Correct 35 ms 5156 KB Output is correct
9 Correct 126 ms 10088 KB Output is correct
10 Correct 143 ms 9584 KB Output is correct
11 Correct 118 ms 9640 KB Output is correct
12 Correct 118 ms 8404 KB Output is correct
13 Correct 106 ms 12212 KB Output is correct
14 Correct 94 ms 6640 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 6652 KB Time limit exceeded
2 Execution timed out 1073 ms 8436 KB Time limit exceeded
3 Execution timed out 1073 ms 11252 KB Time limit exceeded
4 Execution timed out 1022 ms 8704 KB Time limit exceeded
5 Execution timed out 1047 ms 8424 KB Time limit exceeded
6 Execution timed out 1066 ms 8408 KB Time limit exceeded
7 Execution timed out 1069 ms 7540 KB Time limit exceeded
8 Execution timed out 1063 ms 11232 KB Time limit exceeded
9 Execution timed out 1073 ms 10100 KB Time limit exceeded
10 Execution timed out 1079 ms 9588 KB Time limit exceeded
11 Execution timed out 1076 ms 9712 KB Time limit exceeded
12 Execution timed out 1086 ms 8436 KB Time limit exceeded
13 Execution timed out 1074 ms 13168 KB Time limit exceeded
14 Correct 112 ms 6768 KB Output is correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 9972 KB Time limit exceeded
2 Execution timed out 1073 ms 8432 KB Time limit exceeded
3 Correct 108 ms 13292 KB Output is correct
4 Execution timed out 1056 ms 10048 KB Time limit exceeded
5 Execution timed out 1077 ms 9588 KB Time limit exceeded
6 Correct 186 ms 9716 KB Output is correct
7 Execution timed out 1076 ms 8560 KB Time limit exceeded
8 Correct 125 ms 13288 KB Output is correct
9 Correct 67 ms 6768 KB Output is correct