oj.uz

답안 #398723

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
398723 2021-05-04T18:45:01 Z nafis_shifat Ball Machine (BOI13_ballmachine) C++14
100 / 100
 443 ms 28096 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
vector<int> adj[mxn];
int dp[mxn][20];
int level[mxn];
int mn[mxn];
int out[mxn];
int tn[mxn];
int T = 0;
bool on[mxn] = {};

set<int> st;
void dfs1(int cur) {
	mn[cur] = cur;
	for(int u : adj[cur]) {
		level[u] = level[cur] + 1;
		dfs1(u);
		mn[cur] = min(mn[cur],mn[u]);
	}
}

void dfs(int cur) {

	for(int i = 1; i < 20; i++) dp[cur][i] = dp[dp[cur][i - 1]][i - 1];
	for(int u : adj[cur]) {
		dfs(u);
	}
	T++;
	out[cur] = T;
	tn[T] = cur;
	st.insert(T);
}

int dlt(int u) {
	for(int i = 19; i >= 0; i--) {
		if(on[dp[u][i]]) {
			u = dp[u][i];
		}
	}
	on[u] = false;
	st.insert(out[u]);
	return level[u];

}
int main() {
	int n,q;
	cin >> n >> q;
	int root;
	for(int i = 1; i <= n; i++) {
		cin >> dp[i][0];
		if(!dp[i][0]) root = i;
		adj[dp[i][0]].push_back(i); 
	}
	level[root] = 1;
	dfs1(root);
	for(int i = 1; i <= n; i++) {
		sort(adj[i].begin(),adj[i].end(),[](int a,int b) {
			return mn[a] < mn[b];
		});
	}

	dfs(root);

	while(q--) {
		int a,b;
		cin >> a >> b;
		if(a == 1) {
			int ans;
			for(int i = 1; i <= b; i++) {
				int x = *st.begin();
				on[tn[x]] = true;
				ans = tn[x];
				st.erase(x);
			}
			cout<<ans<<endl;

		} else {
			cout<<level[b] - dlt(b)<<endl;
		}
	} 



	
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:79:10: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |    cout<<ans<<endl;
      |          ^~~
ballmachine.cpp:66:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |  dfs(root);
      |  ~~~^~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2656 KB Output is correct
2 Correct 352 ms 14328 KB Output is correct
3 Correct 283 ms 14276 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct
7 Correct 5 ms 2764 KB Output is correct
8 Correct 5 ms 2764 KB Output is correct
9 Correct 27 ms 3404 KB Output is correct
10 Correct 67 ms 5496 KB Output is correct
11 Correct 348 ms 14324 KB Output is correct
12 Correct 285 ms 14228 KB Output is correct
13 Correct 335 ms 14276 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 7720 KB Output is correct
2 Correct 413 ms 23400 KB Output is correct
3 Correct 321 ms 19216 KB Output is correct
4 Correct 246 ms 9444 KB Output is correct
5 Correct 239 ms 9284 KB Output is correct
6 Correct 241 ms 9300 KB Output is correct
7 Correct 242 ms 8516 KB Output is correct
8 Correct 205 ms 7732 KB Output is correct
9 Correct 397 ms 24004 KB Output is correct
10 Correct 415 ms 23452 KB Output is correct
11 Correct 399 ms 23432 KB Output is correct
12 Correct 398 ms 21524 KB Output is correct
13 Correct 349 ms 24892 KB Output is correct
14 Correct 306 ms 19136 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 13252 KB Output is correct
2 Correct 441 ms 22016 KB Output is correct
3 Correct 279 ms 22852 KB Output is correct
4 Correct 263 ms 19536 KB Output is correct
5 Correct 286 ms 19188 KB Output is correct
6 Correct 277 ms 19272 KB Output is correct
7 Correct 273 ms 17828 KB Output is correct
8 Correct 282 ms 22748 KB Output is correct
9 Correct 427 ms 24004 KB Output is correct
10 Correct 440 ms 23596 KB Output is correct
11 Correct 443 ms 23540 KB Output is correct
12 Correct 437 ms 21968 KB Output is correct
13 Correct 441 ms 28096 KB Output is correct
14 Correct 375 ms 19652 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 425 ms 24164 KB Output is correct
2 Correct 432 ms 22024 KB Output is correct
3 Correct 355 ms 27684 KB Output is correct
4 Correct 423 ms 24092 KB Output is correct
5 Correct 426 ms 23596 KB Output is correct
6 Correct 404 ms 23748 KB Output is correct
7 Correct 435 ms 21960 KB Output is correct
8 Correct 353 ms 27716 KB Output is correct
9 Correct 299 ms 19276 KB Output is correct