oj.uz

Submission #55474

# Submission time Handle Problem Language Result Execution time Memory
55474 2018-07-07T15:59:22 Z Diuven Ball Machine (BOI13_ballmachine) C++11
100 / 100
 323 ms 26796 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

int n, q, root;
vector<int> G[MX];
int nu[MX], re[MX], mn[MX];
int st[MX][20];

void dfs1(int v){
    mn[v]=v;
    for(int i=1; i<20; i++) st[v][i]=st[st[v][i-1]][i-1];
    for(int x:G[v]) dfs1(x), mn[v]=min(mn[v], mn[x]);
    sort(G[v].begin(), G[v].end(), [](int a, int b){ return mn[a]<mn[b]; });
}
void dfs2(int v){
    static int now=0;
    for(int x:G[v]) dfs2(x);
    nu[v]=++now; re[nu[v]]=v;
}

set<int> S;
bool B[MX];

int put(){
    int x=*S.begin();
    S.erase(x);
    int v=re[x];
    B[v]=true;
    // cout<<"PLACED: "<<v<<'\n';
    return v;
}

int pop(int v){
    int dist=0;
    for(int i=19; i>=0; i--) if(B[st[v][i]]) v=st[v][i], dist+=(1<<i);
    S.insert(nu[v]);
    B[v]=false;
    return dist;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q;
    for(int i=1; i<=n; i++){
        int p; cin>>p;
        if(p==0) root=i;
        else G[p].push_back(i);
        st[i][0]=p;
    }
    dfs1(root); dfs2(root);
    for(int i=1; i<=n; i++) S.insert(i);

    // for(int i=1; i<=n; i++) cout<<nu[i]<<' ';
    // cout<<'\n';

    for(int i=1; i<=q; i++){
        int t, x; cin>>t>>x;
        if(t==1){
            int ans=0;
            for(; x--; ) ans=put();
            cout<<ans<<'\n';
        }
        else{
            cout<<pop(x)<<'\n';
        }
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2812 KB Output is correct
2 Correct 164 ms 13176 KB Output is correct
3 Correct 87 ms 13216 KB Output is correct
4 Correct 4 ms 13216 KB Output is correct
5 Correct 4 ms 13216 KB Output is correct
6 Correct 5 ms 13216 KB Output is correct
7 Correct 5 ms 13216 KB Output is correct
8 Correct 5 ms 13216 KB Output is correct
9 Correct 11 ms 13216 KB Output is correct
10 Correct 30 ms 13216 KB Output is correct
11 Correct 143 ms 13440 KB Output is correct
12 Correct 89 ms 13440 KB Output is correct
13 Correct 121 ms 13440 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 13440 KB Output is correct
2 Correct 246 ms 22000 KB Output is correct
3 Correct 119 ms 22000 KB Output is correct
4 Correct 76 ms 22000 KB Output is correct
5 Correct 74 ms 22000 KB Output is correct
6 Correct 71 ms 22000 KB Output is correct
7 Correct 76 ms 22000 KB Output is correct
8 Correct 49 ms 22000 KB Output is correct
9 Correct 219 ms 22572 KB Output is correct
10 Correct 194 ms 22572 KB Output is correct
11 Correct 174 ms 22572 KB Output is correct
12 Correct 270 ms 22572 KB Output is correct
13 Correct 187 ms 23724 KB Output is correct
14 Correct 116 ms 23724 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 23724 KB Output is correct
2 Correct 251 ms 23724 KB Output is correct
3 Correct 169 ms 23724 KB Output is correct
4 Correct 154 ms 23724 KB Output is correct
5 Correct 149 ms 23724 KB Output is correct
6 Correct 204 ms 23724 KB Output is correct
7 Correct 199 ms 23724 KB Output is correct
8 Correct 212 ms 23724 KB Output is correct
9 Correct 323 ms 23724 KB Output is correct
10 Correct 281 ms 23724 KB Output is correct
11 Correct 213 ms 23724 KB Output is correct
12 Correct 301 ms 23724 KB Output is correct
13 Correct 230 ms 26796 KB Output is correct
14 Correct 197 ms 26796 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 26796 KB Output is correct
2 Correct 237 ms 26796 KB Output is correct
3 Correct 164 ms 26796 KB Output is correct
4 Correct 316 ms 26796 KB Output is correct
5 Correct 207 ms 26796 KB Output is correct
6 Correct 231 ms 26796 KB Output is correct
7 Correct 291 ms 26796 KB Output is correct
8 Correct 223 ms 26796 KB Output is correct
9 Correct 145 ms 26796 KB Output is correct