oj.uz

Submission #36539

# Submission time Handle Problem Language Result Execution time Memory
36539 2017-12-10T10:39:24 Z Dat160601 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 316 ms 34472 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
int n,q;
int par[100007],mi[100007],root,num[100007],cnt=0;
int op,x;
int p[20][100007];
bool stat[100007];
vector <int> edge[100007],edge2[100007];
priority_queue < pair<int,int> , vector < pair<int,int> > , greater < pair<int,int> > > pr;
void read(int &k){
	int x;
	scanf("%d",&x);
	k=x;
}
void print(int x){
	printf("%d\n",x);
}
void dfs(int u){
	vector < pair<int,int> > cur;
	mi[u]=u;
	for(int i=0;i<(int)edge[u].size();i++){
		int v=edge[u][i];
		if(v==par[u]) continue;
		dfs(v);
		mi[u]=min(mi[u],mi[v]);
		cur.pb(mp(mi[v],v));
	}
	sort(cur.begin(),cur.end());
	for(int i=0;i<(int)cur.size();i++){
		edge2[u].pb(cur[i].se);
	}
}
void dfs2(int u){
	for(int i=0;i<(int)edge2[u].size();i++){
		int v=edge2[u][i];
		if(v==par[u]) continue;
		dfs2(v);
	}
	cnt++;
	num[u]=cnt;
}
int main(){
	read(n);
	read(q);
	for(int i=1;i<=n;i++){
		read(par[i]);
		edge[par[i]].pb(i);
		p[0][i]=par[i];
		if(par[i]==0) root=i;
		mi[i]=1e9;
	}
	dfs(root);
	dfs2(root);
	for(int i=1;i<=n;i++) pr.push(mp(num[i],i));
	for(int i=1;i<=19;i++){
		for(int j=1;j<=n;j++){
			p[i][j]=p[i-1][p[i-1][j]];
		}
	}
	while(q--){
		read(op);
		read(x);
		if(op==1){
			int ans=0;
			while(x>0){
				x--;
				int u=pr.top().se;
				stat[u]=true;
				ans=u;
				pr.pop();
			}
			print(ans);
		}
		else{
			int ans=0;
			for(int i=19;i>=0;i--){
				int pr=p[i][x];
				if(stat[pr]){
					x=pr;
					ans+=(1<<i);
				}
			}
			stat[x]=false;
			pr.push(mp(num[x],x));
			print(ans);
		}
	}
}

Compilation message

ballmachine.cpp: In function 'void read(int&)':
ballmachine.cpp:16:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&x);
                ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15788 KB Output is correct
2 Correct 156 ms 18688 KB Output is correct
3 Correct 106 ms 18688 KB Output is correct
4 Correct 0 ms 15788 KB Output is correct
5 Correct 3 ms 15788 KB Output is correct
6 Correct 0 ms 15788 KB Output is correct
7 Correct 0 ms 15788 KB Output is correct
8 Correct 3 ms 15788 KB Output is correct
9 Correct 3 ms 16056 KB Output is correct
10 Correct 29 ms 16504 KB Output is correct
11 Correct 183 ms 18688 KB Output is correct
12 Correct 106 ms 18688 KB Output is correct
13 Correct 149 ms 18688 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19264 KB Output is correct
2 Correct 213 ms 26656 KB Output is correct
3 Correct 116 ms 20512 KB Output is correct
4 Correct 73 ms 19192 KB Output is correct
5 Correct 83 ms 18936 KB Output is correct
6 Correct 76 ms 18940 KB Output is correct
7 Correct 73 ms 17976 KB Output is correct
8 Correct 39 ms 19260 KB Output is correct
9 Correct 226 ms 27496 KB Output is correct
10 Correct 229 ms 26660 KB Output is correct
11 Correct 263 ms 26660 KB Output is correct
12 Correct 243 ms 23776 KB Output is correct
13 Correct 163 ms 32452 KB Output is correct
14 Correct 103 ms 20512 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 21620 KB Output is correct
2 Correct 316 ms 23924 KB Output is correct
3 Correct 219 ms 31036 KB Output is correct
4 Correct 203 ms 25460 KB Output is correct
5 Correct 179 ms 24784 KB Output is correct
6 Correct 173 ms 24792 KB Output is correct
7 Correct 173 ms 22604 KB Output is correct
8 Correct 209 ms 31036 KB Output is correct
9 Correct 289 ms 27492 KB Output is correct
10 Correct 289 ms 26672 KB Output is correct
11 Correct 263 ms 26672 KB Output is correct
12 Correct 276 ms 23932 KB Output is correct
13 Correct 313 ms 34468 KB Output is correct
14 Correct 169 ms 20520 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 27488 KB Output is correct
2 Correct 236 ms 23932 KB Output is correct
3 Correct 149 ms 34472 KB Output is correct
4 Correct 266 ms 27496 KB Output is correct
5 Correct 269 ms 26668 KB Output is correct
6 Correct 186 ms 26668 KB Output is correct
7 Correct 286 ms 23932 KB Output is correct
8 Correct 159 ms 34472 KB Output is correct
9 Correct 126 ms 20520 KB Output is correct