oj.uz

답안 #140020

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140020 2019-08-01T21:54:10 Z rzbt Ball Machine (BOI13_ballmachine) C++14
100 / 100
 350 ms 32356 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2936 KB Output is correct
2 Correct 195 ms 15852 KB Output is correct
3 Correct 120 ms 15876 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2936 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 7 ms 2936 KB Output is correct
9 Correct 14 ms 3576 KB Output is correct
10 Correct 37 ms 5880 KB Output is correct
11 Correct 195 ms 15948 KB Output is correct
12 Correct 114 ms 15864 KB Output is correct
13 Correct 157 ms 15992 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 8568 KB Output is correct
2 Correct 263 ms 26796 KB Output is correct
3 Correct 148 ms 21876 KB Output is correct
4 Correct 104 ms 10488 KB Output is correct
5 Correct 101 ms 10360 KB Output is correct
6 Correct 97 ms 10360 KB Output is correct
7 Correct 100 ms 9340 KB Output is correct
8 Correct 54 ms 8696 KB Output is correct
9 Correct 236 ms 27384 KB Output is correct
10 Correct 266 ms 26980 KB Output is correct
11 Correct 228 ms 26872 KB Output is correct
12 Correct 260 ms 24480 KB Output is correct
13 Correct 179 ms 28792 KB Output is correct
14 Correct 151 ms 21820 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 15096 KB Output is correct
2 Correct 290 ms 25072 KB Output is correct
3 Correct 187 ms 26300 KB Output is correct
4 Correct 188 ms 22456 KB Output is correct
5 Correct 200 ms 22264 KB Output is correct
6 Correct 204 ms 22212 KB Output is correct
7 Correct 195 ms 20600 KB Output is correct
8 Correct 187 ms 26292 KB Output is correct
9 Correct 349 ms 27648 KB Output is correct
10 Correct 307 ms 27144 KB Output is correct
11 Correct 350 ms 27008 KB Output is correct
12 Correct 319 ms 25076 KB Output is correct
13 Correct 283 ms 32356 KB Output is correct
14 Correct 260 ms 22400 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 257 ms 27608 KB Output is correct
2 Correct 283 ms 25080 KB Output is correct
3 Correct 192 ms 31812 KB Output is correct
4 Correct 282 ms 27640 KB Output is correct
5 Correct 273 ms 27128 KB Output is correct
6 Correct 230 ms 26984 KB Output is correct
7 Correct 279 ms 25056 KB Output is correct
8 Correct 189 ms 32012 KB Output is correct
9 Correct 151 ms 21992 KB Output is correct