oj.uz

답안 #444924

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444924 2021-07-15T21:06:41 Z aryan12 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 244 ms 40596 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e5 + 5;
vector<int> g[N];
int parent[N], minInSubtree[N];
int ranking[N], cnt = 1;
int revRanking[N];
bool isThereBoulder[N];
int DP[20][N];

void dfs(int node) {
	minInSubtree[node] = node;
	for(int i = 0; i < g[node].size(); i++) {
		dfs(g[node][i]);
		minInSubtree[node] = min(minInSubtree[node], minInSubtree[g[node][i]]);
	}
}

void dfs2(int node) {
	int pos, minVal = INT_MAX;
	vector<pair<int, int> > temp;
	for(int i = 0; i < g[node].size(); i++) {
		temp.push_back({minInSubtree[g[node][i]], i});
	}
	sort(temp.begin(), temp.end());
	for(int i = 0; i < temp.size(); i++) {
		dfs2(g[node][temp[i].second]);
	}
	ranking[node] = cnt++;
}

void ComputeDP(int n) {
	for(int i = 1; i < 20; i++) {
		for(int j = 1; j <= n; j++) {
			if(DP[i - 1][j] == -1)
				DP[i][j] = -1;
			else
				DP[i][j] = DP[i - 1][DP[i - 1][j]];
		}
	}
}

void Solve() {
	for(int i = 0; i < N; i++) {
		isThereBoulder[i] = false;
	}
	int n, q;
	cin >> n >> q;
	int root;
	for(int i = 1; i <= n; i++) {
		cin >> parent[i];
		DP[0][i] = parent[i];
		if(parent[i] == 0) {
			root = i;
			DP[0][i] = -1;
		}
		else {
			g[parent[i]].push_back(i);
		}
	}
	ComputeDP(n);
	dfs(root);
	dfs2(root);
	for(int i = 1; i <= n; i++) {
		//cout << ranking[i] << " ";
		revRanking[ranking[i]] = i;
	}
	//cout << "\n";
	priority_queue<int, vector<int>, greater<int> > pq;
	for(int i = 1; i <= n; i++) {
		pq.push(ranking[i]);
	}
	vector<int> ans;
	for(int i = 1; i <= q; i++) {
		int type;
		cin >> type;
		if(type == 1) {
			int boulders;
			cin >> boulders;
			while(boulders != 0) {
				boulders--;
				int curRank = pq.top();
				pq.pop();
				isThereBoulder[revRanking[curRank]] = true;
				if(boulders == 0) {
					ans.push_back(revRanking[curRank]);
				}
			}
		}
		else {
			int crushedNode, res = 0;
			cin >> crushedNode;
			for(int j = 19; j >= 0; j--) {
				if(DP[j][crushedNode] != -1 && isThereBoulder[DP[j][crushedNode]]) {
					crushedNode = DP[j][crushedNode];
					res += (1 << j);
				}
			}
			isThereBoulder[crushedNode] = false;
			pq.push(ranking[crushedNode]);
			ans.push_back(res);
		}
	}
	for(int i = 0; i < ans.size(); i++) {
		cout << ans[i] << "\n";
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
}

Compilation message

ballmachine.cpp: In function 'void dfs(long long int)':
ballmachine.cpp:15:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs2(long long int)':
ballmachine.cpp:24:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
ballmachine.cpp:28:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i = 0; i < temp.size(); i++) {
      |                 ~~^~~~~~~~~~~~~
ballmachine.cpp:22:6: warning: unused variable 'pos' [-Wunused-variable]
   22 |  int pos, minVal = INT_MAX;
      |      ^~~
ballmachine.cpp:22:11: warning: unused variable 'minVal' [-Wunused-variable]
   22 |  int pos, minVal = INT_MAX;
      |           ^~~~~~
ballmachine.cpp: In function 'void Solve()':
ballmachine.cpp:106:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |  for(int i = 0; i < ans.size(); i++) {
      |                 ~~^~~~~~~~~~~~
ballmachine.cpp:65:6: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |  dfs2(root);
      |  ~~~~^~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2892 KB Output is correct
2 Correct 147 ms 18992 KB Output is correct
3 Correct 62 ms 19000 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 3 ms 3036 KB Output is correct
7 Correct 4 ms 3020 KB Output is correct
8 Correct 4 ms 3148 KB Output is correct
9 Correct 8 ms 3940 KB Output is correct
10 Correct 21 ms 6880 KB Output is correct
11 Correct 112 ms 19148 KB Output is correct
12 Correct 74 ms 19000 KB Output is correct
13 Correct 108 ms 18980 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 10992 KB Output is correct
2 Correct 152 ms 33544 KB Output is correct
3 Correct 106 ms 26812 KB Output is correct
4 Correct 74 ms 13396 KB Output is correct
5 Correct 73 ms 13092 KB Output is correct
6 Correct 71 ms 13180 KB Output is correct
7 Correct 63 ms 11652 KB Output is correct
8 Correct 44 ms 10936 KB Output is correct
9 Correct 183 ms 34160 KB Output is correct
10 Correct 175 ms 33636 KB Output is correct
11 Correct 139 ms 34388 KB Output is correct
12 Correct 179 ms 30528 KB Output is correct
13 Correct 121 ms 36804 KB Output is correct
14 Correct 92 ms 26816 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 18548 KB Output is correct
2 Correct 186 ms 30776 KB Output is correct
3 Correct 176 ms 32808 KB Output is correct
4 Correct 135 ms 27296 KB Output is correct
5 Correct 176 ms 27408 KB Output is correct
6 Correct 112 ms 27564 KB Output is correct
7 Correct 121 ms 24792 KB Output is correct
8 Correct 157 ms 32828 KB Output is correct
9 Correct 185 ms 34372 KB Output is correct
10 Correct 197 ms 34508 KB Output is correct
11 Correct 184 ms 33724 KB Output is correct
12 Correct 194 ms 30684 KB Output is correct
13 Correct 244 ms 40596 KB Output is correct
14 Correct 127 ms 27252 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 193 ms 34468 KB Output is correct
2 Correct 197 ms 30688 KB Output is correct
3 Correct 112 ms 40272 KB Output is correct
4 Correct 217 ms 34380 KB Output is correct
5 Correct 207 ms 33920 KB Output is correct
6 Correct 149 ms 34528 KB Output is correct
7 Correct 232 ms 30684 KB Output is correct
8 Correct 144 ms 40264 KB Output is correct
9 Correct 82 ms 26792 KB Output is correct