oj.uz

Submission #206721

# Submission time Handle Problem Language Result Execution time Memory
206721 2020-03-04T17:50:04 Z MvC Ball Machine (BOI13_ballmachine) C++11
100 / 100
 274 ms 33292 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,i,tt,mn[nmax],x,y,p[nmax],par[nmax][20],q,tp,rt,viz[nmax],l[nmax],vl[nmax];
vector<int>a[nmax];
set<pair<int,int> >s;
void dfs(int x)
{
	mn[x]=x;
	vector<pair<int,int> >vc;
	for(int i=0;i<(int)a[x].size();i++)
	{
		int y=a[x][i];
		dfs(y);
		mn[x]=min(mn[x],mn[y]);
		vc.pb(mkp(mn[y],y));
	}
	sort(vc.begin(),vc.end());
	for(int i=0;i<(int)a[x].size();i++)a[x][i]=vc[i].sc;
}
void rec(int x)
{
	for(int i=0;i<(int)a[x].size();i++)rec(a[x][i]);
	vl[x]=++tt;
	s.in(mkp(vl[x],x));
}
void build(int x)
{
	par[x][0]=p[x];
	l[x]=l[p[x]]+1;
	for(int i=1;i<18;i++)par[x][i]=par[par[x][i-1]][i-1];
	for(int i=0;i<(int)a[x].size();i++)build(a[x][i]);
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>q;
	for(i=1;i<=n;i++)
	{
		cin>>p[i];
		if(!p[i])
		{
			rt=i;
			continue;
		}
		a[p[i]].pb(i);
	}
	dfs(rt);
	rec(rt);
	build(rt);
	//for(i=1;i<=n;i++)cout<<vl[i]<<" ";
	//cout<<endl;
	while(q--)
	{
		cin>>tp>>x;
		if(tp==1)
		{
			for(i=1;i<=x;i++)
			{
				y=s.begin()->sc;
				viz[s.begin()->sc]=1;
				s.er(s.begin());
			}
			cout<<y<<'\n';
		}
		else
		{
			y=x;
			for(i=17;i>=0;i--)if(viz[par[y][i]])y=par[y][i];
			cout<<l[x]-l[y]<<'\n';
			s.in(mkp(vl[y],y));
			viz[y]=0;
		}
	}
	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2808 KB Output is correct
2 Correct 164 ms 14584 KB Output is correct
3 Correct 91 ms 14328 KB Output is correct
4 Correct 7 ms 2680 KB Output is correct
5 Correct 7 ms 2808 KB Output is correct
6 Correct 7 ms 2936 KB Output is correct
7 Correct 7 ms 2936 KB Output is correct
8 Correct 7 ms 2936 KB Output is correct
9 Correct 14 ms 3448 KB Output is correct
10 Correct 33 ms 5624 KB Output is correct
11 Correct 182 ms 14656 KB Output is correct
12 Correct 94 ms 14328 KB Output is correct
13 Correct 141 ms 14584 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 8696 KB Output is correct
2 Correct 239 ms 26108 KB Output is correct
3 Correct 123 ms 19300 KB Output is correct
4 Correct 88 ms 10360 KB Output is correct
5 Correct 88 ms 10232 KB Output is correct
6 Correct 83 ms 10232 KB Output is correct
7 Correct 91 ms 8952 KB Output is correct
8 Correct 54 ms 8604 KB Output is correct
9 Correct 234 ms 26616 KB Output is correct
10 Correct 264 ms 26232 KB Output is correct
11 Correct 224 ms 26104 KB Output is correct
12 Correct 232 ms 22904 KB Output is correct
13 Correct 177 ms 29048 KB Output is correct
14 Correct 130 ms 19304 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 14712 KB Output is correct
2 Correct 254 ms 23544 KB Output is correct
3 Correct 166 ms 26872 KB Output is correct
4 Correct 156 ms 21752 KB Output is correct
5 Correct 165 ms 21372 KB Output is correct
6 Correct 176 ms 21476 KB Output is correct
7 Correct 155 ms 19192 KB Output is correct
8 Correct 178 ms 26872 KB Output is correct
9 Correct 252 ms 27000 KB Output is correct
10 Correct 257 ms 26360 KB Output is correct
11 Correct 262 ms 26488 KB Output is correct
12 Correct 246 ms 23544 KB Output is correct
13 Correct 274 ms 33292 KB Output is correct
14 Correct 180 ms 20072 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 26872 KB Output is correct
2 Correct 241 ms 23544 KB Output is correct
3 Correct 179 ms 32592 KB Output is correct
4 Correct 235 ms 26904 KB Output is correct
5 Correct 238 ms 26360 KB Output is correct
6 Correct 209 ms 26360 KB Output is correct
7 Correct 240 ms 23544 KB Output is correct
8 Correct 190 ms 32504 KB Output is correct
9 Correct 113 ms 19308 KB Output is correct