Submission #283435

#	Time	Username	Problem	Language	Result	Execution time	Memory
283435		Fasho	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	481 ms	34152 KiB

ballmachine

#include <bits/stdc++.h>
#define N 100005
#define ll long long int
#define fo(i,x,y)	for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll> 
#define fast2 freopen ("in.txt","r",stdin);freopen ("out.txt","w",stdout);
#define mod 1000000007
using namespace std;

ll n,m,ar[N],sum,t,tut1[N],cnt,tut[N],dad[N][19],mark[N],deg[N];

vector<int> v[N];

bool cmp(int a,int b)
{
	return tut1[a]<tut1[b];
}

void f1(int ind,int back,int dg)
{
	ll mn=ind;
	deg[ind]=dg;
	dad[ind][0]=back;
	for(int i=1;i<=17;i++)
		dad[ind][i]=dad[dad[ind][i-1]][i-1];
	for(int i=0;i<v[ind].size();i++)
	{
		ll x=v[ind][i];
		if(x!=back)
			f1(x,ind,dg+1);
		mn=min(mn,tut1[x]);
	}
	tut1[ind]=mn;
	return;
}
void f(int ind,int back)
{
	for(int i=0;i<v[ind].size();i++)
	{
		ll x=v[ind][i];
		if(x!=back)
			f(x,ind);
	}
	tut[ind]=++cnt;
}

struct node{
	int a;
};

bool operator<(node a,node b)
{
	return tut[a.a]>tut[b.a];
}

priority_queue<node> pq;

ll f2(int ind)
{
	for(int i=18;i>=0;i--)
		if(mark[dad[ind][i]])
			ind=dad[ind][i];
	return ind;
}


int main()
{
	fast;
	cin>>n>>m;
	int rt=1;
	fo(i,1,n)
	{
		ll a;
		cin>>a;
		if(a==0)
			rt=i;
		v[a].pb(i);
	}
	f1(rt,0,0);
	fo(i,1,n)
		sort(v[i].begin(),v[i].end(),cmp);
	f(rt,0);
	ll top=0;
	fo(i,1,n)
	{
		node tt;
		tt.a=i;
		pq.push(tt);
	}
	fo(i,1,m)
	{
		int a,b;
		cin>>a>>b;
		if(a==1)
		{
			ll x=0;
			fo(i,1,b)
			{
				x=pq.top().a;
				pq.pop();
				mark[x]=1;
			}
			cout<<x<<endl;
		}
		else
		{
			ll x=f2(b);
			ll y=deg[b]-deg[x];
			node tt;
			tt.a=x;
			pq.push({tt});
			mark[x]=0;
			cout<<y<<endl;
		}
	}



	// cout<<tut1[i]<<sp;
} 

Compilation message (stderr)

ballmachine.cpp: In function 'void f1(int, int, int)':
ballmachine.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=0;i<v[ind].size();i++)
      |              ~^~~~~~~~~~~~~~
ballmachine.cpp: In function 'void f(int, int)':
ballmachine.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0;i<v[ind].size();i++)
      |              ~^~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:92:5: warning: unused variable 'top' [-Wunused-variable]
   92 |  ll top=0;
      |     ^~~

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5