oj.uz

답안 #897200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897200 2024-01-02T17:29:46 Z Mathias Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 1000 ms 26964 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+7;
const int LOG = 19;
int jp[MAXN][LOG];
int ojciec[MAXN];
int depth[MAXN];
int post[MAXN];
bool ball[MAXN];
vector<int> g[MAXN];
set<pair<int,int> > s;
int cnt=0;
void DFS(int x){
	depth[x]=depth[ojciec[x]]+1;
	jp[x][0]=ojciec[x];
	for(int i=1;i<LOG;i++) jp[x][i]=jp[jp[x][i-1]][i-1];
	for(int i=0;i<g[x].size();i++){
		DFS(g[x][i]);
	}
	s.insert({++cnt,x});
	post[x]=cnt;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,q,x,r,a,b;
	pair<int,int> p;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>x;
		ojciec[i]=x;
		if(x==0) r=i;
		else g[x].push_back(i);
	}
	for(int i=1;i<=n;i++) sort(g[i].begin(), g[i].end());
	DFS(r);
	for(int i=1;i<=n;i++) for(int j=0;j<LOG;j++) if(jp[i][j]==0) jp[i][j]=r;	
	while(q--){
		cin>>a>>b;
		if(a==1){
			while(b--){
				auto it=s.begin();
				s.erase(it);
				p=*it;
				ball[p.second]=1;
				if(b==0){
					cout<<p.second<<'\n';
				}
			}
		}
		else{
			x=b;
			for(int i=LOG-1;i>=0;i--){
				if(ball[jp[x][i]]==1){
					x=jp[x][i];
				}	
			}
			ball[x]=0;
			s.insert({post[x],x});
			//cout<<b<<' '<<x<<'\n';
			cout<<depth[b]-depth[x]<<'\n';
		}
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'void DFS(int)':
ballmachine.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0;i<g[x].size();i++){
      |              ~^~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:36:71: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |  for(int i=1;i<=n;i++) for(int j=0;j<LOG;j++) if(jp[i][j]==0) jp[i][j]=r;
      |                                                               ~~~~~~~~^~

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4700 KB Output isn't correct
2 Execution timed out 1065 ms 15956 KB Time limit exceeded
3 Incorrect 48 ms 16040 KB Output isn't correct
4 Execution timed out 1055 ms 4700 KB Time limit exceeded
5 Incorrect 1 ms 4700 KB Output isn't correct
6 Incorrect 3 ms 4700 KB Output isn't correct
7 Execution timed out 1035 ms 4744 KB Time limit exceeded
8 Execution timed out 1042 ms 4696 KB Time limit exceeded
9 Incorrect 7 ms 4956 KB Output isn't correct
10 Execution timed out 1064 ms 8028 KB Time limit exceeded
11 Incorrect 84 ms 16208 KB Output isn't correct
12 Incorrect 69 ms 15900 KB Output isn't correct
13 Incorrect 74 ms 15956 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 10076 KB Output is correct
2 Incorrect 115 ms 22608 KB Output isn't correct
3 Incorrect 64 ms 18544 KB Output isn't correct
4 Execution timed out 1042 ms 10324 KB Time limit exceeded
5 Execution timed out 1038 ms 9868 KB Time limit exceeded
6 Incorrect 49 ms 10580 KB Output isn't correct
7 Incorrect 53 ms 9824 KB Output isn't correct
8 Correct 33 ms 9972 KB Output is correct
9 Incorrect 117 ms 22860 KB Output isn't correct
10 Incorrect 127 ms 22516 KB Output isn't correct
11 Incorrect 93 ms 22356 KB Output isn't correct
12 Incorrect 102 ms 20308 KB Output isn't correct
13 Correct 70 ms 24400 KB Output is correct
14 Incorrect 59 ms 18488 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 14564 KB Output isn't correct
2 Incorrect 116 ms 21072 KB Output isn't correct
3 Correct 67 ms 23112 KB Output is correct
4 Incorrect 70 ms 20036 KB Output isn't correct
5 Incorrect 90 ms 19808 KB Output isn't correct
6 Incorrect 119 ms 19644 KB Output isn't correct
7 Incorrect 71 ms 18400 KB Output isn't correct
8 Correct 68 ms 23124 KB Output is correct
9 Incorrect 112 ms 23024 KB Output isn't correct
10 Incorrect 115 ms 22852 KB Output isn't correct
11 Incorrect 115 ms 22612 KB Output isn't correct
12 Incorrect 135 ms 21076 KB Output isn't correct
13 Correct 157 ms 26964 KB Output is correct
14 Incorrect 105 ms 18640 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 103 ms 22864 KB Output isn't correct
2 Incorrect 162 ms 20984 KB Output isn't correct
3 Correct 78 ms 26708 KB Output is correct
4 Incorrect 112 ms 22868 KB Output isn't correct
5 Incorrect 173 ms 22356 KB Output isn't correct
6 Incorrect 139 ms 22356 KB Output isn't correct
7 Incorrect 130 ms 20824 KB Output isn't correct
8 Correct 82 ms 26612 KB Output is correct
9 Incorrect 64 ms 18480 KB Output isn't correct