Submission #140020

#	Time	Username	Problem	Language	Result	Execution time	Memory
140020		rzbt	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	350 ms	32356 KiB

ballmachine

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;

using namespace std;

int n,q;
vector<int> niz[MAXN];
int seg[4*MAXN],org[MAXN];
int koren;
int ulaz[MAXN],izlaz[MAXN];
int zaovo[MAXN];
int prioritet[MAXN],OP[MAXN];
int predak[MAXN][21];
int dubina[MAXN];
int vreme=0;
set<int> svi;
bool zauzet[MAXN];
void dfs(int t){
    vreme++;
    ulaz[t]=vreme;
    org[vreme]=t;
    for(auto x:niz[t]){
        dfs(x);
    }
    izlaz[t]=vreme;
}

void izgradi(int l,int d,int k){
    if(l==d)seg[k]=org[l];
    else{
        int mid=(l+d)/2;
        izgradi(l,mid,k+k);
        izgradi(mid+1,d,k+k+1);
        seg[k]=min(seg[k+k],seg[k+k+1]);
    }
}
int dobij(int l,int d,int tl,int td,int k){
    if(l>=tl && d<=td)return seg[k];
    if(l>td || d<tl)return n+1;


    int mid=(l+d)/2;
    return min(dobij(l,mid,tl,td,k+k),dobij(mid+1,d,tl,td,k+k+1));
}
bool cmp(int a,int b){
    return zaovo[a]<zaovo[b];
}

void dfs2(int t,int h){

    dubina[t]=h;
    org[vreme]=t;
    sort(all(niz[t]),cmp);

    for(auto x:niz[t]){
        dfs2(x,h+1);
    }
    vreme++;
    prioritet[vreme]=t;
    OP[t]=vreme;
}


int main()
{
    scanf("%d %d", &n, &q);
    for(int i=1;i<=n;i++){
        svi.insert(i);
        int t;
        scanf("%d", &t);
        predak[i][0]=t;
        if(t==0)koren=i;
        else niz[t].pb(i);
    }
    dfs(koren);
    izgradi(1,n,1);
    vreme=0;

    for(int i=1;i<=n;i++)zaovo[i]=dobij(1,n,ulaz[i],izlaz[i],1);
    dfs2(koren,0);
    //for(int i=1;i<=n;i++)printf("%d ",prioritet[i]);

    for(int j=1;j<21;j++){
        for(int i=1;i<=n;i++){
            predak[i][j]=predak[predak[i][j-1]][j-1];
        }
    }
    //////////////////////

    while(q--){
        int qt,k;
        scanf("%d %d", &qt, &k);
        if(qt==1){
            while(k--){
                zauzet[prioritet[*(svi.begin())]]=true;
                if(k==0)printf("%d\n",prioritet[*(svi.begin())]);
                svi.erase(svi.begin());
            }
        }else{
            int od=dubina[k];
            for(int j=20;j>=0;j--){
                if(zauzet[predak[k][j]])k=predak[k][j];
            }
            printf("%d\n",od-dubina[k]);
            svi.insert(OP[k]);
            zauzet[k]=false;
        }
    }


    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &t);
         ~~~~~^~~~~~~~~~
ballmachine.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &qt, &k);
         ~~~~~^~~~~~~~~~~~~~~~~~

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