oj.uz

답안 #102680

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102680 2019-03-26T17:59:16 Z rubenvd Ball Machine (BOI13_ballmachine) C++14
100 / 100
 271 ms 22352 KB 
#include <bits/stdc++.h>
using namespace std;
int par[100005][20], val[100005], num = 0, numD = 0, place[100005];
bool filled[100005];
vector<int> child[100005], topo, path;
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 ){
	path.push_back(u);
	int mini = 1e9;
	for( auto v : child[u] )
		mini = min(dfs(v), mini);

	place[u] = topo.size();
	topo.push_back(u);

	/*cout << u << endl;
	for( int i = 0; i < path.size(); ++i )
		cout << path[i] << " ";
	cout << endl;*/

	for( int i = 1; i < 17 && (1<<i) < path.size(); i++ )
		par[u][i] = path[path.size() - (1<<i) - 1];

	val[u] = min(u, mini);
	path.pop_back();
	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 sum = 0, i = 0;
	//cout << u << " : " << endl;
	while( filled[par[u][i]] == true ){
		//cout << par[u][i] << " " << filled[par[u][i]] << endl;
		i++;
	}

	if( i == 0 ){
		deleted.push(place[u]);
		filled[u] = false;
		return 0;
	} else {
		sum = (1<<(i-1)) + del(par[u][i-1]);
		return sum;
	}
}

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][0];
		child[par[i][0]].push_back(i);
		if( par[i][0] == 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 <= n; ++i ){
		for( int j = 0; j < 5; ++j ){
			cout << par[i][j] << " ";
		}
		cout << endl;
	}*/

	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 dfs(int)':
ballmachine.cpp:26:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for( int i = 1; i < 17 && (1<<i) < path.size(); i++ )
                            ~~~~~~~^~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for( int i = 0; i < topo.size(); ++i )
                  ~~^~~~~~~~~~~~~
ballmachine.cpp: In function 'int add(int)':
ballmachine.cpp:42:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return last;
         ^~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:82:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(root);
  ~~~^~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 103 ms 10868 KB Output is correct
3 Correct 90 ms 11096 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 4 ms 2816 KB Output is correct
8 Correct 5 ms 2816 KB Output is correct
9 Correct 8 ms 3200 KB Output is correct
10 Correct 19 ms 4800 KB Output is correct
11 Correct 121 ms 10888 KB Output is correct
12 Correct 90 ms 11080 KB Output is correct
13 Correct 117 ms 10868 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 6880 KB Output is correct
2 Correct 174 ms 17624 KB Output is correct
3 Correct 90 ms 14448 KB Output is correct
4 Correct 57 ms 7928 KB Output is correct
5 Correct 70 ms 7860 KB Output is correct
6 Correct 64 ms 7840 KB Output is correct
7 Correct 81 ms 7376 KB Output is correct
8 Correct 45 ms 6904 KB Output is correct
9 Correct 200 ms 18000 KB Output is correct
10 Correct 164 ms 17768 KB Output is correct
11 Correct 143 ms 17524 KB Output is correct
12 Correct 160 ms 16052 KB Output is correct
13 Correct 154 ms 19440 KB Output is correct
14 Correct 86 ms 14512 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 10844 KB Output is correct
2 Correct 216 ms 17308 KB Output is correct
3 Correct 157 ms 18284 KB Output is correct
4 Correct 149 ms 15384 KB Output is correct
5 Correct 137 ms 15056 KB Output is correct
6 Correct 128 ms 15240 KB Output is correct
7 Correct 143 ms 14424 KB Output is correct
8 Correct 172 ms 18168 KB Output is correct
9 Correct 211 ms 18800 KB Output is correct
10 Correct 223 ms 18420 KB Output is correct
11 Correct 271 ms 18508 KB Output is correct
12 Correct 221 ms 17160 KB Output is correct
13 Correct 242 ms 22352 KB Output is correct
14 Correct 139 ms 14448 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 18928 KB Output is correct
2 Correct 187 ms 17480 KB Output is correct
3 Correct 156 ms 21524 KB Output is correct
4 Correct 212 ms 18864 KB Output is correct
5 Correct 209 ms 18260 KB Output is correct
6 Correct 201 ms 17724 KB Output is correct
7 Correct 179 ms 17560 KB Output is correct
8 Correct 164 ms 21480 KB Output is correct
9 Correct 91 ms 14448 KB Output is correct