oj.uz

답안 #102338

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102338 2019-03-24T11:17:13 Z rubenvd Ball Machine (BOI13_ballmachine) C++14
55.7937 / 100
 1000 ms 12796 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();
	}

	for( num; cnt > 0 && num < topo.size(); cnt-- ){
		last = topo[num];
		filled[topo[num]] = true;
		num++;
	}
	return last;
}

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

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

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

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 = 0; i < n; ++i )
		sort(child[i].begin(), child[i].end(), compareInt);
	topo.clear();
	dfs(root);

	for( int i= 0; i < q; ++i ){
		cin >> type >> k;
		if( type == 1 ){
			int out = add(k);
			cout << out << "\n";
		} else {
			cout << del(k) << "\n";
		}
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'int add(int)':
ballmachine.cpp:34:10: warning: statement has no effect [-Wunused-value]
  for( num; cnt > 0 && num < topo.size(); cnt-- ){
          ^
ballmachine.cpp:34:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for( num; cnt > 0 && num < topo.size(); cnt-- ){
                       ~~~~^~~~~~~~~~~~~
ballmachine.cpp:39:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return last;
         ^~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:75:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(root);
  ~~~^~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2688 KB Output is correct
2 Correct 100 ms 5236 KB Output is correct
3 Correct 75 ms 5384 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 5 ms 2688 KB Output is correct
8 Correct 5 ms 2816 KB Output is correct
9 Correct 8 ms 2944 KB Output is correct
10 Correct 24 ms 3456 KB Output is correct
11 Correct 63 ms 5360 KB Output is correct
12 Correct 57 ms 5364 KB Output is correct
13 Correct 80 ms 5108 KB Output is correct

Subtask #2
25.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 4856 KB Output is correct
2 Correct 131 ms 9476 KB Output is correct
3 Correct 80 ms 6256 KB Output is correct
4 Correct 47 ms 4984 KB Output is correct
5 Incorrect 40 ms 4856 KB Output isn't correct
6 Incorrect 51 ms 4728 KB Output isn't correct
7 Correct 51 ms 4476 KB Output is correct
8 Correct 51 ms 4856 KB Output is correct
9 Correct 118 ms 9716 KB Output is correct
10 Correct 125 ms 9328 KB Output is correct
11 Correct 108 ms 8952 KB Output is correct
12 Correct 107 ms 8168 KB Output is correct
13 Correct 144 ms 11608 KB Output is correct
14 Correct 74 ms 6228 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1065 ms 6356 KB Time limit exceeded
2 Execution timed out 1069 ms 7912 KB Time limit exceeded
3 Execution timed out 1081 ms 10616 KB Time limit exceeded
4 Execution timed out 1077 ms 8180 KB Time limit exceeded
5 Execution timed out 1079 ms 7928 KB Time limit exceeded
6 Execution timed out 1077 ms 7920 KB Time limit exceeded
7 Execution timed out 1079 ms 6912 KB Time limit exceeded
8 Execution timed out 1073 ms 10616 KB Time limit exceeded
9 Execution timed out 1063 ms 9496 KB Time limit exceeded
10 Execution timed out 1076 ms 8952 KB Time limit exceeded
11 Execution timed out 1082 ms 8952 KB Time limit exceeded
12 Execution timed out 1077 ms 7692 KB Time limit exceeded
13 Execution timed out 1079 ms 12404 KB Time limit exceeded
14 Correct 79 ms 6640 KB Output is correct

Subtask #4
2.22222222222 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1074 ms 9336 KB Time limit exceeded
2 Execution timed out 1072 ms 7792 KB Time limit exceeded
3 Correct 122 ms 12796 KB Output is correct
4 Execution timed out 1080 ms 9448 KB Time limit exceeded
5 Execution timed out 1072 ms 9332 KB Time limit exceeded
6 Correct 171 ms 9076 KB Output is correct
7 Execution timed out 1082 ms 7792 KB Time limit exceeded
8 Correct 114 ms 12780 KB Output is correct
9 Correct 69 ms 6160 KB Output is correct