oj.uz

답안 #897279

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897279 2024-01-02T20:57:39 Z Mathias Ball Machine (BOI13_ballmachine) C++14
100 / 100
 155 ms 31152 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);
	//cout<<"x="<<x<<" cnt+1="<<cnt+1<<'\n';
	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);
	}
	ojciec[r]=r;
	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();
				p=*it;
				//cout<<b<<' '<<p.first<<' '<<p.second<<'\n';
				ball[p.second]=1;
				if(b==0){
					cout<<p.second<<'\n';
				}
				s.erase(it);
			}
		}
		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';
		}
		//for(int i=1;i<=n;i++){
		//	cout<<ball[i]<<' ';
		//}
		//cout<<'\n';
		//for (auto it = s.begin(); it != s.end(); it++){
		//	p=*it;
		//	cout<<p.second<<' ';
		//} 
		//cout<<'\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:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i=0;i<g[x].size();i++){
      |              ~^~~~~~~~~~~~
ballmachine.cpp:31:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  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:46:5: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |  DFS(r);
      |  ~~~^~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 79 ms 15176 KB Output is correct
3 Correct 56 ms 15336 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 6 ms 7012 KB Output is correct
10 Correct 16 ms 7772 KB Output is correct
11 Correct 91 ms 15084 KB Output is correct
12 Correct 52 ms 15184 KB Output is correct
13 Correct 72 ms 14936 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 10320 KB Output is correct
2 Correct 113 ms 24144 KB Output is correct
3 Correct 67 ms 18124 KB Output is correct
4 Correct 48 ms 10576 KB Output is correct
5 Correct 49 ms 10580 KB Output is correct
6 Correct 46 ms 10452 KB Output is correct
7 Correct 52 ms 9560 KB Output is correct
8 Correct 28 ms 10328 KB Output is correct
9 Correct 100 ms 24404 KB Output is correct
10 Correct 131 ms 24140 KB Output is correct
11 Correct 99 ms 24444 KB Output is correct
12 Correct 104 ms 21104 KB Output is correct
13 Correct 78 ms 28024 KB Output is correct
14 Correct 65 ms 18120 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 15440 KB Output is correct
2 Correct 123 ms 21632 KB Output is correct
3 Correct 85 ms 26088 KB Output is correct
4 Correct 75 ms 21168 KB Output is correct
5 Correct 91 ms 20840 KB Output is correct
6 Correct 79 ms 20820 KB Output is correct
7 Correct 90 ms 18516 KB Output is correct
8 Correct 82 ms 26044 KB Output is correct
9 Correct 110 ms 24660 KB Output is correct
10 Correct 118 ms 24404 KB Output is correct
11 Correct 138 ms 24404 KB Output is correct
12 Correct 124 ms 21784 KB Output is correct
13 Correct 155 ms 31152 KB Output is correct
14 Correct 103 ms 18124 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 24912 KB Output is correct
2 Correct 149 ms 21832 KB Output is correct
3 Correct 93 ms 31060 KB Output is correct
4 Correct 110 ms 24668 KB Output is correct
5 Correct 116 ms 24468 KB Output is correct
6 Correct 116 ms 24404 KB Output is correct
7 Correct 113 ms 21568 KB Output is correct
8 Correct 89 ms 30952 KB Output is correct
9 Correct 63 ms 18108 KB Output is correct