oj.uz

Submission #283435

# Submission time Handle Problem Language Result Execution time Memory
283435 2020-08-25T18:42:45 Z Fasho Ball Machine (BOI13_ballmachine) C++14
100 / 100
 481 ms 34152 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 349 ms 17268 KB Output is correct
3 Correct 310 ms 16756 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 4 ms 2944 KB Output is correct
7 Correct 5 ms 2944 KB Output is correct
8 Correct 6 ms 2944 KB Output is correct
9 Correct 25 ms 3584 KB Output is correct
10 Correct 69 ms 6272 KB Output is correct
11 Correct 361 ms 17236 KB Output is correct
12 Correct 306 ms 16884 KB Output is correct
13 Correct 327 ms 17400 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 8824 KB Output is correct
2 Correct 463 ms 28664 KB Output is correct
3 Correct 316 ms 23024 KB Output is correct
4 Correct 252 ms 11128 KB Output is correct
5 Correct 252 ms 11104 KB Output is correct
6 Correct 248 ms 11128 KB Output is correct
7 Correct 249 ms 9980 KB Output is correct
8 Correct 217 ms 8824 KB Output is correct
9 Correct 405 ms 29044 KB Output is correct
10 Correct 434 ms 28660 KB Output is correct
11 Correct 411 ms 28784 KB Output is correct
12 Correct 433 ms 26220 KB Output is correct
13 Correct 370 ms 29556 KB Output is correct
14 Correct 329 ms 23152 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 15992 KB Output is correct
2 Correct 469 ms 26940 KB Output is correct
3 Correct 309 ms 27588 KB Output is correct
4 Correct 278 ms 23860 KB Output is correct
5 Correct 289 ms 23540 KB Output is correct
6 Correct 282 ms 23376 KB Output is correct
7 Correct 279 ms 21876 KB Output is correct
8 Correct 312 ms 27636 KB Output is correct
9 Correct 441 ms 29428 KB Output is correct
10 Correct 452 ms 28784 KB Output is correct
11 Correct 443 ms 28916 KB Output is correct
12 Correct 431 ms 26996 KB Output is correct
13 Correct 472 ms 34152 KB Output is correct
14 Correct 353 ms 24304 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 29368 KB Output is correct
2 Correct 441 ms 26860 KB Output is correct
3 Correct 375 ms 33008 KB Output is correct
4 Correct 462 ms 29428 KB Output is correct
5 Correct 481 ms 28916 KB Output is correct
6 Correct 405 ms 28788 KB Output is correct
7 Correct 459 ms 27100 KB Output is correct
8 Correct 372 ms 33008 KB Output is correct
9 Correct 324 ms 23060 KB Output is correct