Submission #944058

#	Time	Username	Problem	Language	Result	Execution time	Memory
944058		tamir1	Ball Machine (BOI13_ballmachine)	C++17	59.92 / 100	1091 ms	16984 KiB

ballmachine

#include<bits/stdc++.h>
#define ll int
#define ff first
#define ss second
using namespace std;
ll n,q,i,p[100005],sz[100005],root,x,y,u[100005],a[100005];
bitset<100005> vis;
vector<pair<ll,ll>> v[100005];
vector<ll> w[100005],t[100005];
pair<ll,ll> loc[100005];
void dfs(ll x){
	for(ll i:t[x]){
		dfs(i);
		a[x]=min(a[i],a[x]);
	}
}
ll update(ll x){
	ll idx=0;
	for(pair<ll,ll> i:v[x]){
		if(sz[i.ss]<w[i.ss].size()){
			idx=i.ss;
			break;
		}
	}
	if(idx!=0) return update(idx);
	else{
		sz[x]++;
		return w[x][sz[x]-1];
	}
}
ll roll(ll x){
	ll y=loc[x].ff,z=loc[x].ss;
	if(sz[y]<w[y].size() || sz[p[y]]==0){
		sz[y]--;
		return sz[y]-z+2;
	}
	return sz[y]-z+1+roll(p[y]);
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> q;
	for(i=1;i<=n;i++){
		loc[i]={i,1};
		w[i].push_back(i);
		cin >> p[i];
		a[i]=i;
		u[p[i]]++;
	}
	for(i=1;i<=n;i++){
		if(u[i]==0){
			x=i;
			while(p[x]!=0){
				y=p[x];
				if(vis[x]==1) break;
				vis[x]=1;
				if(u[y]==1){
					p[x]=p[y];
					p[y]=-1;
					w[x].push_back(y);
					loc[y]={x,w[x].size()};
					a[x]=min(a[x],a[y]);
					vis[x]=0;
				}
				else x=y;
			}
		}
	}
	for(i=1;i<=n;i++){
		if(p[i]==-1) continue;
		if(p[i]==0) root=i;
		else t[p[i]].push_back(i);
	}
	dfs(root);
	for(i=1;i<=n;i++){
		if(p[i]!=-1 && p[i]!=0){
			v[p[i]].push_back({a[i],i});
		}
	}
	for(i=1;i<=n;i++){
		sort(v[i].begin(),v[i].end());
	}
	while(q--){
		cin >> x >> y;
		if(x==1){
			for(i=1;i<=y;i++)
				x=update(root);
			cout << x << "\n";
		}
		else{
			cout << roll(y)-1 << "\n";
		}
	}
} 

Compilation message (stderr)

ballmachine.cpp: In function 'int update(int)':
ballmachine.cpp:20:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   if(sz[i.ss]<w[i.ss].size()){
      |      ~~~~~~~~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int roll(int)':
ballmachine.cpp:33:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  if(sz[y]<w[y].size() || sz[p[y]]==0){
      |     ~~~~~^~~~~~~~~~~~

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