oj.uz

Submission #102313

# Submission time Handle Problem Language Result Execution time Memory
102313 2019-03-24T09:55:53 Z rubenvd Ball Machine (BOI13_ballmachine) C++11
40.7143 / 100
 1000 ms 11436 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;
		return {u, cnt-1};
	}
	else{
		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(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	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:79: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 4 ms 2816 KB Output is correct
2 Correct 212 ms 4576 KB Output is correct
3 Correct 203 ms 4728 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 24 ms 2944 KB Output is correct
10 Correct 55 ms 3200 KB Output is correct
11 Correct 232 ms 4700 KB Output is correct
12 Correct 206 ms 4728 KB Output is correct
13 Correct 185 ms 4460 KB Output is correct

Subtask #2
12.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 4452 KB Time limit exceeded
2 Correct 272 ms 7972 KB Output is correct
3 Execution timed out 1070 ms 5424 KB Time limit exceeded
4 Correct 162 ms 4600 KB Output is correct
5 Incorrect 171 ms 4572 KB Output isn't correct
6 Incorrect 262 ms 4636 KB Output isn't correct
7 Correct 168 ms 4060 KB Output is correct
8 Execution timed out 1062 ms 4420 KB Time limit exceeded
9 Correct 264 ms 8696 KB Output is correct
10 Correct 269 ms 8060 KB Output is correct
11 Execution timed out 1066 ms 8220 KB Time limit exceeded
12 Correct 270 ms 6908 KB Output is correct
13 Execution timed out 1056 ms 10488 KB Time limit exceeded
14 Execution timed out 1073 ms 5212 KB Time limit exceeded

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1041 ms 5988 KB Time limit exceeded
2 Execution timed out 1078 ms 6828 KB Time limit exceeded
3 Execution timed out 1069 ms 9884 KB Time limit exceeded
4 Execution timed out 1065 ms 7416 KB Time limit exceeded
5 Execution timed out 1058 ms 7040 KB Time limit exceeded
6 Execution timed out 1049 ms 7144 KB Time limit exceeded
7 Execution timed out 1072 ms 6008 KB Time limit exceeded
8 Execution timed out 1070 ms 9856 KB Time limit exceeded
9 Execution timed out 1049 ms 8360 KB Time limit exceeded
10 Execution timed out 1057 ms 7924 KB Time limit exceeded
11 Execution timed out 1037 ms 8056 KB Time limit exceeded
12 Execution timed out 1067 ms 6756 KB Time limit exceeded
13 Execution timed out 1084 ms 11436 KB Time limit exceeded
14 Correct 256 ms 5108 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 8312 KB Time limit exceeded
2 Execution timed out 1041 ms 6880 KB Time limit exceeded
3 Execution timed out 1057 ms 11420 KB Time limit exceeded
4 Execution timed out 1048 ms 8356 KB Time limit exceeded
5 Execution timed out 1052 ms 8188 KB Time limit exceeded
6 Execution timed out 1065 ms 8192 KB Time limit exceeded
7 Execution timed out 1050 ms 6876 KB Time limit exceeded
8 Execution timed out 1047 ms 11384 KB Time limit exceeded
9 Execution timed out 1067 ms 5184 KB Time limit exceeded