oj.uz

답안 #493486

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
493486 2021-12-11T15:45:39 Z _Monkey_ Ball Machine (BOI13_ballmachine) C++17
100 / 100
 141 ms 21164 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define el '\n'
const int maxn=1e5+1,oo=1e9;
void amin(int &x,int y){ if(x>y) x=y;}
void amax(int &x,int y){ if(x<y) x=y;}

int n,m,opt,o,cnt,k,u,val,ans;
vector<vector<int>> con,far;
vector<int> cha,minn,ut,reut,st;
vector<bool> ok;

// trade 1
bool check(int x,int y){
    return minn[x]<minn[y];
}
int prepare(int z){
    minn[z]=z;
    for(int &e:con[z]) amin(minn[z],prepare(e));
    return minn[z];
}
void dfs(int z){
    for(int &e:con[z]) dfs(e);
    cnt++;
    ut[z]=cnt;
    reut[cnt]=z;
    return;
}
void pre_up(int id,int l,int r){
    if(r<u || l>u) return;
    if(l==r){
        st[id]+=val;
        return;
    }
    int mid=(l+r)/2;
    pre_up(id*2,l,mid);
    pre_up(id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
    return;
}
void up(int id,int v){
    u=id;
    val=v;
    return pre_up(1,1,n);
}
void pre_get(int id,int l,int r){
    if(l==r){
        ans=l;
        ok[l]=1;
        up(l,1);
        return;
    }
    int mid=(l+r)/2;
    if(mid-l+1==st[id*2]) pre_get(id*2+1,mid+1,r);
    else pre_get(id*2,l,mid);
}
void get(){
    return pre_get(1,1,n);
}

// trade 2

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n >> m;
    con.resize(n+1);
    cha.resize(n+1);
    minn.resize(n+1);
    ut.resize(n+1);
    reut.resize(n+1);
    st.resize(n*4+1);
    ok.resize(n+1);
    far.resize(18,vector<int> (n+1));

    for(int i=1;i<=n;++i){
        cin >> cha[i];
        con[ cha[i] ].push_back(i);
    }
    opt=con[0][0];
    prepare(opt);
    for(int i=1;i<=n;++i) sort(con[i].begin(),con[i].end(),check);
    dfs(opt);

    for(int i=1;i<=n;++i) far[0][ut[i]]=ut[cha[i]];
    for(int i=1;i<18;++i){
        for(int j=1;j<=n;++j){
            far[i][j]=far[i-1][ far[i-1][j] ];
        }
    }
    while(m--){
        cin >> o >> k;
        if(o==1){
            for(int i=0;i<k;++i) get();
            cout << reut[ans] << el;
        } else {
            cnt=0;
            k=ut[k];
            for(int i=17;i>=0;--i) if(ok[ far[i][k] ]){
                cnt+=(1<<i);
                k=far[i][k];
            }
            up(k,-1);
            ok[k]=0;
            cout << cnt << el;
        }
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 94 ms 9904 KB Output is correct
3 Correct 53 ms 9984 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 6 ms 892 KB Output is correct
10 Correct 19 ms 2636 KB Output is correct
11 Correct 89 ms 9756 KB Output is correct
12 Correct 51 ms 10028 KB Output is correct
13 Correct 87 ms 9832 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 4244 KB Output is correct
2 Correct 119 ms 17340 KB Output is correct
3 Correct 62 ms 14380 KB Output is correct
4 Correct 57 ms 5620 KB Output is correct
5 Correct 58 ms 5488 KB Output is correct
6 Correct 54 ms 5524 KB Output is correct
7 Correct 57 ms 4684 KB Output is correct
8 Correct 34 ms 4292 KB Output is correct
9 Correct 97 ms 17720 KB Output is correct
10 Correct 106 ms 17344 KB Output is correct
11 Correct 104 ms 17296 KB Output is correct
12 Correct 112 ms 15808 KB Output is correct
13 Correct 73 ms 18740 KB Output is correct
14 Correct 63 ms 14412 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 9016 KB Output is correct
2 Correct 135 ms 16448 KB Output is correct
3 Correct 81 ms 16940 KB Output is correct
4 Correct 74 ms 14320 KB Output is correct
5 Correct 74 ms 13956 KB Output is correct
6 Correct 78 ms 13960 KB Output is correct
7 Correct 76 ms 13064 KB Output is correct
8 Correct 92 ms 16932 KB Output is correct
9 Correct 119 ms 17908 KB Output is correct
10 Correct 141 ms 17508 KB Output is correct
11 Correct 129 ms 17664 KB Output is correct
12 Correct 131 ms 16328 KB Output is correct
13 Correct 124 ms 21164 KB Output is correct
14 Correct 125 ms 14400 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 18108 KB Output is correct
2 Correct 135 ms 16264 KB Output is correct
3 Correct 89 ms 21048 KB Output is correct
4 Correct 116 ms 17980 KB Output is correct
5 Correct 111 ms 17460 KB Output is correct
6 Correct 110 ms 17468 KB Output is correct
7 Correct 118 ms 16272 KB Output is correct
8 Correct 84 ms 21072 KB Output is correct
9 Correct 67 ms 14416 KB Output is correct