oj.uz

답안 #897229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897229 2024-01-02T18:46:15 Z Mathias Ball Machine (BOI13_ballmachine) C++14
14.2857 / 100
 1000 ms 31056 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){
	//cout<<"wchodze x="<<x<<'\n';
	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]});
		//cout<<g[x][i]<<' '<<mini[g[x][i]]<<'\n';
	}
	sort(vec.begin(),vec.end());
	for(int i=0;i<vec.size();i++) DFS(vec[i].second);
	s.insert({++cnt,x});
	post[x]=cnt;
	//cout<<"wychodze x="<<x<<'\n';
}
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],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);
	}
	//cout<<"r="<<r<<'\n';

	DFS1(r);
	//for(int i=1;i<=n;i++) cout<<mini[i]<<' '; cout<<'\n';
	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--){
				//cout<<b<<'\n';
				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({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:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<g[x].size();i++){
      |              ~^~~~~~~~~~~~
ballmachine.cpp:26: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]
   26 |  for(int i=0;i<vec.size();i++) DFS(vec[i].second);
      |              ~^~~~~~~~~~~
ballmachine.cpp: In function 'void DFS1(int)':
ballmachine.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i=0;i<g[x].size();i++){
      |              ~^~~~~~~~~~~~
ballmachine.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<g[x].size();i++) mini[x]=min(mini[x],g[x][i]);
      |              ~^~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:54:71: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |  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 4696 KB Output isn't correct
2 Execution timed out 1061 ms 15040 KB Time limit exceeded
3 Incorrect 51 ms 15152 KB Output isn't correct
4 Execution timed out 1057 ms 4700 KB Time limit exceeded
5 Incorrect 1 ms 4696 KB Output isn't correct
6 Incorrect 1 ms 4700 KB Output isn't correct
7 Execution timed out 1059 ms 4700 KB Time limit exceeded
8 Incorrect 2 ms 4696 KB Output isn't correct
9 Incorrect 6 ms 7004 KB Output isn't correct
10 Execution timed out 1095 ms 7772 KB Time limit exceeded
11 Incorrect 83 ms 14928 KB Output isn't correct
12 Incorrect 49 ms 15188 KB Output isn't correct
13 Incorrect 71 ms 15020 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 10484 KB Output isn't correct
2 Incorrect 127 ms 24404 KB Output isn't correct
3 Incorrect 70 ms 18120 KB Output isn't correct
4 Execution timed out 1049 ms 10576 KB Time limit exceeded
5 Incorrect 58 ms 11092 KB Output isn't correct
6 Incorrect 54 ms 10588 KB Output isn't correct
7 Incorrect 51 ms 9664 KB Output isn't correct
8 Incorrect 35 ms 10588 KB Output isn't correct
9 Incorrect 112 ms 24480 KB Output isn't correct
10 Incorrect 117 ms 24276 KB Output isn't correct
11 Incorrect 110 ms 24404 KB Output isn't correct
12 Incorrect 123 ms 21388 KB Output isn't correct
13 Incorrect 78 ms 27948 KB Output isn't correct
14 Incorrect 64 ms 18296 KB Output isn't correct

Subtask #3
14.2857142857 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 15188 KB Output is correct
2 Incorrect 123 ms 21704 KB Output isn't correct
3 Correct 100 ms 26460 KB Output is correct
4 Incorrect 76 ms 21072 KB Output isn't correct
5 Incorrect 80 ms 20980 KB Output isn't correct
6 Incorrect 82 ms 20848 KB Output isn't correct
7 Incorrect 81 ms 18548 KB Output isn't correct
8 Correct 90 ms 26196 KB Output is correct
9 Incorrect 124 ms 24584 KB Output isn't correct
10 Incorrect 124 ms 24520 KB Output isn't correct
11 Incorrect 147 ms 24496 KB Output isn't correct
12 Incorrect 138 ms 21840 KB Output isn't correct
13 Correct 134 ms 31056 KB Output is correct
14 Correct 107 ms 18120 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 137 ms 24760 KB Output isn't correct
2 Incorrect 128 ms 21800 KB Output isn't correct
3 Incorrect 93 ms 30972 KB Output isn't correct
4 Incorrect 116 ms 24680 KB Output isn't correct
5 Incorrect 139 ms 24660 KB Output isn't correct
6 Incorrect 121 ms 24520 KB Output isn't correct
7 Incorrect 127 ms 21672 KB Output isn't correct
8 Incorrect 90 ms 30976 KB Output isn't correct
9 Incorrect 65 ms 18124 KB Output isn't correct