oj.uz

Submission #897245

# Submission time Handle Problem Language Result Execution time Memory
897245 2024-01-02T19:45:11 Z Mathias Ball Machine (BOI13_ballmachine) C++14
48.9072 / 100
 1000 ms 31392 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 mini[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];
	vector<pair<int,int> > vec;
	for(int i=0;i<g[x].size();i++) vec.push_back({mini[g[x][i]], g[x][i]});
	sort(vec.begin(),vec.end());
	for(int i=0;i<vec.size();i++) DFS(vec[i].second);
	s.insert({++cnt,x});
	post[x]=cnt;
}
void DFS1(int x){
	for(int i=0;i<g[x].size();i++){
		DFS1(g[x][i]);
	}
	mini[x]=x;
	for(int i=0;i<g[x].size();i++) mini[x]=min(mini[x],mini[g[x][i]]);
}
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);
	}
	DFS1(r);
	DFS(r);	
	//for(int i=1;i<=n;i++) cout<<mini[i]<<' '; cout<<'\n';
	while(q--){
		cin>>a>>b;
		if(a==1){
			while(b--){
				auto it=s.begin();
				s.erase(it);
				p=*it;
				//cout<<p.second<<'\n';
				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({mini[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:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0;i<g[x].size();i++) vec.push_back({mini[g[x][i]], g[x][i]});
      |              ~^~~~~~~~~~~~
ballmachine.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<vec.size();i++) DFS(vec[i].second);
      |              ~^~~~~~~~~~~
ballmachine.cpp: In function 'void DFS1(int)':
ballmachine.cpp:26:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i=0;i<g[x].size();i++){
      |              ~^~~~~~~~~~~~
ballmachine.cpp:30:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i=0;i<g[x].size();i++) mini[x]=min(mini[x],mini[g[x][i]]);
      |              ~^~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:44:5: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |  DFS(r);
      |  ~~~^~~

Subtask #1
1.92307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4696 KB Output isn't correct
2 Incorrect 103 ms 15048 KB Output isn't correct
3 Incorrect 48 ms 15036 KB Output isn't correct
4 Execution timed out 1022 ms 4696 KB Time limit exceeded
5 Incorrect 1 ms 4700 KB Output isn't correct
6 Correct 1 ms 4700 KB Output is correct
7 Execution timed out 1056 ms 4700 KB Time limit exceeded
8 Incorrect 2 ms 4696 KB Output isn't correct
9 Incorrect 6 ms 7000 KB Output isn't correct
10 Execution timed out 1040 ms 7968 KB Time limit exceeded
11 Incorrect 81 ms 14928 KB Output isn't correct
12 Incorrect 48 ms 15080 KB Output isn't correct
13 Incorrect 82 ms 15268 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 10584 KB Output isn't correct
2 Incorrect 133 ms 24360 KB Output isn't correct
3 Correct 62 ms 18120 KB Output is correct
4 Execution timed out 1071 ms 10836 KB Time limit exceeded
5 Incorrect 56 ms 10576 KB Output isn't correct
6 Incorrect 60 ms 11288 KB Output isn't correct
7 Incorrect 51 ms 9516 KB Output isn't correct
8 Incorrect 27 ms 10456 KB Output isn't correct
9 Correct 111 ms 24512 KB Output is correct
10 Incorrect 122 ms 24400 KB Output isn't correct
11 Incorrect 130 ms 24432 KB Output isn't correct
12 Incorrect 118 ms 21332 KB Output isn't correct
13 Incorrect 80 ms 27892 KB Output isn't correct
14 Correct 62 ms 18120 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 15108 KB Output is correct
2 Correct 122 ms 22140 KB Output is correct
3 Correct 90 ms 26192 KB Output is correct
4 Correct 79 ms 21076 KB Output is correct
5 Correct 82 ms 20816 KB Output is correct
6 Correct 81 ms 20820 KB Output is correct
7 Correct 83 ms 18676 KB Output is correct
8 Correct 88 ms 26368 KB Output is correct
9 Correct 135 ms 24992 KB Output is correct
10 Correct 141 ms 25080 KB Output is correct
11 Correct 132 ms 24660 KB Output is correct
12 Correct 134 ms 21724 KB Output is correct
13 Correct 156 ms 31392 KB Output is correct
14 Correct 114 ms 18548 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 24868 KB Output isn't correct
2 Incorrect 126 ms 21808 KB Output isn't correct
3 Incorrect 86 ms 31060 KB Output isn't correct
4 Incorrect 138 ms 25172 KB Output isn't correct
5 Incorrect 132 ms 24340 KB Output isn't correct
6 Incorrect 113 ms 24404 KB Output isn't correct
7 Incorrect 122 ms 21844 KB Output isn't correct
8 Incorrect 115 ms 31320 KB Output isn't correct
9 Correct 63 ms 18224 KB Output is correct