oj.uz

Submission #102310

# Submission time Handle Problem Language Result Execution time Memory
102310 2019-03-24T09:37:42 Z rubenvd Ball Machine (BOI13_ballmachine) C++14
40.7143 / 100
 1000 ms 11576 KB 
#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;
		//cout << "  " << u << " " << cnt-1 << endl;
		return {u, cnt-1};
	}
	else{
		//cout << " " << ret.first << " " << cnt << endl;
		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(){
	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

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2816 KB Output is correct
2 Correct 294 ms 4524 KB Output is correct
3 Correct 233 ms 4728 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 7 ms 2816 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 8 ms 2816 KB Output is correct
9 Correct 21 ms 2816 KB Output is correct
10 Correct 51 ms 3072 KB Output is correct
11 Correct 306 ms 4640 KB Output is correct
12 Correct 235 ms 4740 KB Output is correct
13 Correct 235 ms 4472 KB Output is correct

Subtask #2
12.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 4396 KB Time limit exceeded
2 Correct 336 ms 8116 KB Output is correct
3 Execution timed out 1074 ms 5236 KB Time limit exceeded
4 Correct 203 ms 4856 KB Output is correct
5 Incorrect 250 ms 4472 KB Output isn't correct
6 Incorrect 257 ms 4472 KB Output isn't correct
7 Correct 183 ms 4136 KB Output is correct
8 Execution timed out 1070 ms 4520 KB Time limit exceeded
9 Correct 391 ms 8440 KB Output is correct
10 Correct 362 ms 8184 KB Output is correct
11 Execution timed out 1071 ms 8212 KB Time limit exceeded
12 Correct 312 ms 6904 KB Output is correct
13 Execution timed out 1072 ms 10360 KB Time limit exceeded
14 Execution timed out 1070 ms 5356 KB Time limit exceeded

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 5984 KB Time limit exceeded
2 Execution timed out 1061 ms 6904 KB Time limit exceeded
3 Execution timed out 1066 ms 9740 KB Time limit exceeded
4 Execution timed out 1066 ms 7608 KB Time limit exceeded
5 Execution timed out 1065 ms 7260 KB Time limit exceeded
6 Execution timed out 1086 ms 7160 KB Time limit exceeded
7 Execution timed out 1075 ms 6136 KB Time limit exceeded
8 Execution timed out 1070 ms 9880 KB Time limit exceeded
9 Execution timed out 1071 ms 8348 KB Time limit exceeded
10 Execution timed out 1078 ms 8060 KB Time limit exceeded
11 Execution timed out 1083 ms 8088 KB Time limit exceeded
12 Execution timed out 1084 ms 6780 KB Time limit exceeded
13 Execution timed out 1056 ms 11576 KB Time limit exceeded
14 Correct 307 ms 5236 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 8420 KB Time limit exceeded
2 Execution timed out 1066 ms 6804 KB Time limit exceeded
3 Execution timed out 1075 ms 11384 KB Time limit exceeded
4 Execution timed out 1075 ms 8568 KB Time limit exceeded
5 Execution timed out 1073 ms 8184 KB Time limit exceeded
6 Execution timed out 1081 ms 8288 KB Time limit exceeded
7 Execution timed out 1081 ms 7036 KB Time limit exceeded
8 Execution timed out 1087 ms 11384 KB Time limit exceeded
9 Execution timed out 1074 ms 5280 KB Time limit exceeded