Submission #42700

#	Time	Username	Problem	Language	Result	Execution time	Memory
42700		Hassoony	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	214 ms	25028 KiB

ballmachine

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=2e5+9;
const ll mod=1e8+6;
int n,q,dp[20][MX],ball[MX],mn[MX],timer,out[MX],x,t,root;
bool cmp(int A,int B){
    return mn[A]<mn[B];
}
vector<int>v[MX];
priority_queue<pair<int,int> >pq;
void dfs(int x){
    for(auto pp:v[x]){
        dfs(pp);
        mn[x]=min(mn[x],mn[pp]);
    }
    sort(v[x].begin(),v[x].end(),cmp);
}
void build(){
    for(int i=1;i<=18;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=dp[i-1][dp[i-1][j]];
}
void pro(int x){
    for(auto pp:v[x])pro(pp);
    out[x]=++timer;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        mn[i]=i;
        scanf("%d",&dp[0][i]);
        if(dp[0][i]==0){root=i;continue;}
        v[dp[0][i]].push_back(i);
    }
    dfs(root);
    build();
    pro(root);
    for(int i=1;i<=n;i++)pq.push({-out[i],i});
    while(q--){
        scanf("%d%d",&t,&x);
        if(t==1){
            int last=0;
            while(x--){
                ball[pq.top().second]=1;
                last=pq.top().second;
                pq.pop();
            }
            printf("%d\n",last);
        }
        else{
            int ans=0;
            for(int i=18;i>=0;i--){
                if(ball[dp[i][x]]){
                    x=dp[i][x];
                    ans+=(1<<i);
                }
            }
            ball[x]=0;
            pq.push({-out[x],x});
            printf("%d\n",ans);
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:29:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&q);
                        ^
ballmachine.cpp:32:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&dp[0][i]);
                              ^
ballmachine.cpp:41:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&t,&x);
                            ^

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