oj.uz

Submission #199448

# Submission time Handle Problem Language Result Execution time Memory
199448 2020-02-01T12:50:46 Z TadijaSebez Ball Machine (BOI13_ballmachine) C++11
98.0769 / 100
 516 ms 24928 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
vector<int> E[N];
int sz[N],mn[N],hc[N];
void DFS(int u){
	sz[u]=1;mn[u]=u;
	for(int v:E[u])
		DFS(v),
		sz[u]+=sz[v],
		mn[u]=min(mn[u],mn[v]),
		hc[u]=sz[v]>sz[hc[u]]?v:hc[u];
}
int idx[N],isz;
void IDF(int u){
	sort(E[u].begin(),E[u].end(),[&](int i,int j){return mn[i]<mn[j];});
	for(int v:E[u])IDF(v);
	idx[u]=++isz;
}
int lid[N],rid[N],nod[N],dep[N],tid,head[N];
void HLD(int u){
	if(!head[u])head[u]=u;
	for(int i=0;i<E[u].size();i++)if(E[u][i]==hc[u])swap(E[u][i],E[u][0]);
	lid[u]=++tid;
	nod[tid]=u;
	if(hc[u])head[hc[u]]=head[u];
	for(int v:E[u])dep[v]=dep[u]+1,HLD(v);
	rid[u]=tid;
}
const int M=2*N;
int ls[M],rs[M],tsz,root,sum[M];
void Set(int &c,int ss,int se,int qi,int f){
	if(!c)c=++tsz;
	if(ss==se){sum[c]=f;return;}
	int mid=ss+se>>1;
	if(qi<=mid)Set(ls[c],ss,mid,qi,f);
	else Set(rs[c],mid+1,se,qi,f);
	sum[c]=sum[ls[c]]+sum[rs[c]];
}
int Search(int c,int ss,int se,int k){
	if(ss==se)return sum[c]==k?ss:ss-1;
	int mid=ss+se>>1;
	if(sum[rs[c]]>=k)return Search(rs[c],mid+1,se,k);
	else return Search(ls[c],ss,mid,k-sum[rs[c]]);
}
int Get(int c,int ss,int se,int qs,int qe){
	if(qs>qe || qs>se || ss>qe)return 0;
	if(qs<=ss && qe>=se)return sum[c];
	int mid=ss+se>>1;
	return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
int Search(int ss,int se){return Search(root,1,N,Get(root,1,N,ss,N));}
int par[N];
int main(){
	int n,q;
	scanf("%i %i",&n,&q);
	for(int i=1;i<=n;i++)scanf("%i",&par[i]),E[par[i]].pb(i);
	int rt=E[0][0];
	DFS(rt);
	IDF(rt);
	HLD(rt);
	set<pair<int,int>> avb;
	for(int i=1;i<=n;i++)avb.insert({idx[i],i});
	while(q--){
		int t,k;
		scanf("%i %i",&t,&k);
		if(t==1){
			int las=-1;
			while(k--){
				auto p=*avb.begin();
				avb.erase(p);
				Set(root,1,N,lid[p.second],1);
				las=p.second;
			}
			printf("%i\n",las);
		}else{
			int u=k,las=k,ans;
			while(u){
				int v=Search(lid[head[u]],lid[u]);
				//printf("%i %i %i %i\n",head[u],u,nod[v],v);
				if(v>lid[u]){ans=las;break;}
				else if(v==lid[head[u]]){
					las=head[u];
					u=par[head[u]];
				}else{ans=nod[v];break;}
			}
			if(u==0)ans=las;
			//int ans=k;
			//printf("ans: %i\n",ans);
			printf("%i\n",dep[k]-dep[ans]);
			avb.insert({idx[ans],ans});
			Set(root,1,N,lid[ans],0);
		}
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'void HLD(int)':
ballmachine.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++)if(E[u][i]==hc[u])swap(E[u][i],E[u][0]);
              ~^~~~~~~~~~~~
ballmachine.cpp: In function 'void Set(int&, int, int, int, int)':
ballmachine.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
ballmachine.cpp: In function 'int Search(int, int, int, int)':
ballmachine.cpp:43:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
ballmachine.cpp: In function 'int Get(int, int, int, int, int)':
ballmachine.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
ballmachine.cpp:58:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%i",&par[i]),E[par[i]].pb(i);
                       ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&t,&k);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
23.0769230769 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2680 KB Output is correct
2 Execution timed out 331 ms 12024 KB Time limit exceeded (wall clock)
3 Correct 138 ms 10744 KB Output is correct
4 Correct 7 ms 2808 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 8 ms 2808 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 9 ms 2936 KB Output is correct
9 Correct 22 ms 3320 KB Output is correct
10 Correct 54 ms 4984 KB Output is correct
11 Correct 362 ms 12056 KB Output is correct
12 Correct 122 ms 10872 KB Output is correct
13 Correct 248 ms 10872 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6904 KB Output is correct
2 Correct 341 ms 19448 KB Output is correct
3 Correct 152 ms 13784 KB Output is correct
4 Correct 145 ms 8528 KB Output is correct
5 Correct 133 ms 8348 KB Output is correct
6 Correct 118 ms 7852 KB Output is correct
7 Correct 141 ms 7548 KB Output is correct
8 Correct 62 ms 6904 KB Output is correct
9 Correct 329 ms 19704 KB Output is correct
10 Correct 360 ms 19504 KB Output is correct
11 Correct 271 ms 18152 KB Output is correct
12 Correct 337 ms 17200 KB Output is correct
13 Correct 203 ms 20192 KB Output is correct
14 Correct 177 ms 13864 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 11764 KB Output is correct
2 Correct 516 ms 18912 KB Output is correct
3 Correct 258 ms 19832 KB Output is correct
4 Correct 291 ms 16632 KB Output is correct
5 Correct 264 ms 16292 KB Output is correct
6 Correct 283 ms 16324 KB Output is correct
7 Correct 204 ms 15012 KB Output is correct
8 Correct 256 ms 19828 KB Output is correct
9 Correct 431 ms 20888 KB Output is correct
10 Correct 457 ms 20604 KB Output is correct
11 Correct 421 ms 20776 KB Output is correct
12 Correct 458 ms 18912 KB Output is correct
13 Correct 365 ms 24928 KB Output is correct
14 Correct 443 ms 16620 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 20080 KB Output is correct
2 Correct 447 ms 18296 KB Output is correct
3 Correct 232 ms 22264 KB Output is correct
4 Correct 339 ms 20088 KB Output is correct
5 Correct 375 ms 19464 KB Output is correct
6 Correct 270 ms 18068 KB Output is correct
7 Correct 428 ms 18220 KB Output is correct
8 Correct 185 ms 22268 KB Output is correct
9 Correct 164 ms 13940 KB Output is correct