oj.uz

Submission #897178

# Submission time Handle Problem Language Result Execution time Memory
897178 2024-01-02T16:55:45 Z Mathias Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 1000 ms 25936 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);
	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:35:5: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |  DFS(r);
      |  ~~~^~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4700 KB Output isn't correct
2 Execution timed out 1057 ms 15188 KB Time limit exceeded
3 Incorrect 55 ms 15308 KB Output isn't correct
4 Execution timed out 1040 ms 4696 KB Time limit exceeded
5 Incorrect 1 ms 4696 KB Output isn't correct
6 Incorrect 2 ms 4768 KB Output isn't correct
7 Execution timed out 1092 ms 4700 KB Time limit exceeded
8 Execution timed out 1072 ms 4700 KB Time limit exceeded
9 Incorrect 5 ms 4956 KB Output isn't correct
10 Execution timed out 1057 ms 7772 KB Time limit exceeded
11 Incorrect 101 ms 15468 KB Output isn't correct
12 Incorrect 48 ms 15188 KB Output isn't correct
13 Incorrect 66 ms 15060 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9560 KB Output is correct
2 Incorrect 131 ms 21584 KB Output isn't correct
3 Incorrect 59 ms 17744 KB Output isn't correct
4 Execution timed out 1076 ms 9820 KB Time limit exceeded
5 Execution timed out 1077 ms 9564 KB Time limit exceeded
6 Incorrect 47 ms 10076 KB Output isn't correct
7 Incorrect 61 ms 9452 KB Output isn't correct
8 Correct 24 ms 9564 KB Output is correct
9 Incorrect 110 ms 21964 KB Output isn't correct
10 Incorrect 130 ms 21588 KB Output isn't correct
11 Incorrect 106 ms 21364 KB Output isn't correct
12 Incorrect 102 ms 19660 KB Output isn't correct
13 Correct 67 ms 23632 KB Output is correct
14 Incorrect 57 ms 17872 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 13912 KB Output isn't correct
2 Incorrect 109 ms 20048 KB Output isn't correct
3 Correct 88 ms 22316 KB Output is correct
4 Incorrect 67 ms 19032 KB Output isn't correct
5 Incorrect 73 ms 18884 KB Output isn't correct
6 Incorrect 75 ms 18808 KB Output isn't correct
7 Incorrect 71 ms 17592 KB Output isn't correct
8 Correct 87 ms 22464 KB Output is correct
9 Incorrect 105 ms 21844 KB Output isn't correct
10 Incorrect 121 ms 21588 KB Output isn't correct
11 Incorrect 110 ms 21648 KB Output isn't correct
12 Incorrect 105 ms 19852 KB Output isn't correct
13 Correct 108 ms 25904 KB Output is correct
14 Incorrect 97 ms 17576 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 21832 KB Output isn't correct
2 Incorrect 112 ms 19792 KB Output isn't correct
3 Correct 76 ms 25932 KB Output is correct
4 Incorrect 103 ms 21920 KB Output isn't correct
5 Incorrect 109 ms 21584 KB Output isn't correct
6 Incorrect 111 ms 21524 KB Output isn't correct
7 Incorrect 107 ms 20036 KB Output isn't correct
8 Correct 109 ms 25936 KB Output is correct
9 Incorrect 59 ms 17636 KB Output isn't correct