Submission #199448

#	Time	Username	Problem	Language	Result	Execution time	Memory
199448		TadijaSebez	Ball Machine (BOI13_ballmachine)	C++11	98.08 / 100	516 ms	24928 KiB

ballmachine

#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 (stderr)

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.076923076923077 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5