oj.uz

Submission #102311

# Submission time Handle Problem Language Result Execution time Memory
102311 2019-03-24T09:41:27 Z rubenvd Ball Machine (BOI13_ballmachine) C++14
40.7143 / 100
 1000 ms 11384 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 5 ms 2816 KB Output is correct
2 Correct 233 ms 4632 KB Output is correct
3 Correct 216 ms 4820 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 6 ms 2816 KB Output is correct
8 Correct 8 ms 2816 KB Output is correct
9 Correct 18 ms 2944 KB Output is correct
10 Correct 43 ms 3200 KB Output is correct
11 Correct 244 ms 4472 KB Output is correct
12 Correct 181 ms 4652 KB Output is correct
13 Correct 188 ms 4500 KB Output is correct

Subtask #2
12.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 4408 KB Time limit exceeded
2 Correct 274 ms 8052 KB Output is correct
3 Execution timed out 1073 ms 5144 KB Time limit exceeded
4 Correct 160 ms 4656 KB Output is correct
5 Incorrect 176 ms 4600 KB Output isn't correct
6 Incorrect 236 ms 4496 KB Output isn't correct
7 Correct 160 ms 4024 KB Output is correct
8 Execution timed out 1035 ms 4472 KB Time limit exceeded
9 Correct 259 ms 8696 KB Output is correct
10 Correct 268 ms 8096 KB Output is correct
11 Execution timed out 1022 ms 8072 KB Time limit exceeded
12 Correct 294 ms 6904 KB Output is correct
13 Execution timed out 1071 ms 10360 KB Time limit exceeded
14 Execution timed out 1080 ms 5368 KB Time limit exceeded

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 5880 KB Time limit exceeded
2 Execution timed out 1082 ms 6780 KB Time limit exceeded
3 Execution timed out 1076 ms 9760 KB Time limit exceeded
4 Execution timed out 1081 ms 7288 KB Time limit exceeded
5 Execution timed out 1069 ms 7164 KB Time limit exceeded
6 Execution timed out 1059 ms 7220 KB Time limit exceeded
7 Execution timed out 1067 ms 6244 KB Time limit exceeded
8 Execution timed out 1082 ms 9848 KB Time limit exceeded
9 Execution timed out 1064 ms 8440 KB Time limit exceeded
10 Execution timed out 1057 ms 8000 KB Time limit exceeded
11 Execution timed out 1067 ms 8044 KB Time limit exceeded
12 Execution timed out 1074 ms 6904 KB Time limit exceeded
13 Execution timed out 1079 ms 11384 KB Time limit exceeded
14 Correct 233 ms 5236 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 8592 KB Time limit exceeded
2 Execution timed out 1075 ms 6904 KB Time limit exceeded
3 Execution timed out 1081 ms 11384 KB Time limit exceeded
4 Execution timed out 1069 ms 8440 KB Time limit exceeded
5 Execution timed out 1065 ms 8112 KB Time limit exceeded
6 Execution timed out 1073 ms 8184 KB Time limit exceeded
7 Execution timed out 1078 ms 6904 KB Time limit exceeded
8 Execution timed out 1072 ms 11384 KB Time limit exceeded
9 Execution timed out 1076 ms 5164 KB Time limit exceeded