oj.uz

답안 #102534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102534 2019-03-25T18:42:21 Z rubenvd Ball Machine (BOI13_ballmachine) C++14
55.7937 / 100
 1000 ms 14316 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();
	}
	
	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 < topo.size(); ++i )
		deleted.push(place[topo[i]]);

	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 main()':
ballmachine.cpp:71: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:34:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return last;
         ^~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:70:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(root);
  ~~~^~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 81 ms 6484 KB Output is correct
3 Correct 63 ms 6516 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 2816 KB Output is correct
8 Correct 4 ms 2816 KB Output is correct
9 Correct 7 ms 2944 KB Output is correct
10 Correct 17 ms 3584 KB Output is correct
11 Correct 66 ms 6480 KB Output is correct
12 Correct 53 ms 6516 KB Output is correct
13 Correct 75 ms 6512 KB Output is correct

Subtask #2
25.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 5468 KB Output is correct
2 Correct 128 ms 10768 KB Output is correct
3 Correct 65 ms 7408 KB Output is correct
4 Correct 56 ms 5728 KB Output is correct
5 Incorrect 56 ms 5624 KB Output isn't correct
6 Incorrect 64 ms 5624 KB Output isn't correct
7 Correct 42 ms 5120 KB Output is correct
8 Correct 30 ms 5496 KB Output is correct
9 Correct 99 ms 11016 KB Output is correct
10 Correct 103 ms 10732 KB Output is correct
11 Correct 99 ms 10612 KB Output is correct
12 Correct 150 ms 9576 KB Output is correct
13 Correct 105 ms 13040 KB Output is correct
14 Correct 74 ms 7452 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1064 ms 6936 KB Time limit exceeded
2 Execution timed out 1069 ms 9072 KB Time limit exceeded
3 Execution timed out 1090 ms 11636 KB Time limit exceeded
4 Execution timed out 1073 ms 9200 KB Time limit exceeded
5 Execution timed out 1087 ms 8820 KB Time limit exceeded
6 Execution timed out 1084 ms 8824 KB Time limit exceeded
7 Execution timed out 1080 ms 8052 KB Time limit exceeded
8 Execution timed out 1084 ms 11636 KB Time limit exceeded
9 Execution timed out 1084 ms 10612 KB Time limit exceeded
10 Execution timed out 1073 ms 10224 KB Time limit exceeded
11 Execution timed out 1071 ms 10228 KB Time limit exceeded
12 Execution timed out 1078 ms 8948 KB Time limit exceeded
13 Execution timed out 1079 ms 13796 KB Time limit exceeded
14 Correct 113 ms 7796 KB Output is correct

Subtask #4
2.22222222222 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1084 ms 10612 KB Time limit exceeded
2 Execution timed out 1081 ms 9068 KB Time limit exceeded
3 Correct 124 ms 14316 KB Output is correct
4 Execution timed out 1082 ms 10612 KB Time limit exceeded
5 Execution timed out 1080 ms 10356 KB Time limit exceeded
6 Correct 212 ms 10740 KB Output is correct
7 Execution timed out 1070 ms 9152 KB Time limit exceeded
8 Correct 121 ms 14192 KB Output is correct
9 Correct 76 ms 7280 KB Output is correct