oj.uz

Submission #55461

# Submission time Handle Problem Language Result Execution time Memory
55461 2018-07-07T15:19:15 Z Diuven Ball Machine (BOI13_ballmachine) C++11
16.1111 / 100
 356 ms 70472 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];
int st[MX][20];

void dfs(int v){
    static int now=0;
    for(int i=1; i<20; i++) st[v][i]=st[st[v][i-1]][i-1];
    for(int x:G[v]) dfs(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;
    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;
    }
    dfs(root);
    for(int i=1; i<=n; i++) S.insert(i);

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

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Incorrect 118 ms 14124 KB Output isn't correct
3 Incorrect 110 ms 15328 KB Output isn't correct
4 Incorrect 5 ms 15328 KB Output isn't correct
5 Incorrect 4 ms 15328 KB Output isn't correct
6 Incorrect 5 ms 15328 KB Output isn't correct
7 Incorrect 6 ms 15328 KB Output isn't correct
8 Incorrect 5 ms 15328 KB Output isn't correct
9 Incorrect 10 ms 15328 KB Output isn't correct
10 Incorrect 29 ms 15328 KB Output isn't correct
11 Incorrect 203 ms 16800 KB Output isn't correct
12 Incorrect 87 ms 17896 KB Output isn't correct
13 Incorrect 123 ms 18948 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 18948 KB Output is correct
2 Incorrect 202 ms 28864 KB Output isn't correct
3 Incorrect 110 ms 28864 KB Output isn't correct
4 Incorrect 119 ms 28864 KB Output isn't correct
5 Incorrect 109 ms 28864 KB Output isn't correct
6 Incorrect 95 ms 28864 KB Output isn't correct
7 Incorrect 102 ms 28864 KB Output isn't correct
8 Correct 45 ms 28864 KB Output is correct
9 Incorrect 284 ms 35084 KB Output isn't correct
10 Incorrect 268 ms 36196 KB Output isn't correct
11 Incorrect 152 ms 37376 KB Output isn't correct
12 Incorrect 172 ms 37376 KB Output isn't correct
13 Correct 215 ms 40852 KB Output is correct
14 Incorrect 131 ms 40852 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 40852 KB Output isn't correct
2 Incorrect 356 ms 41644 KB Output isn't correct
3 Correct 178 ms 43112 KB Output is correct
4 Incorrect 173 ms 43112 KB Output isn't correct
5 Incorrect 193 ms 43112 KB Output isn't correct
6 Incorrect 194 ms 43112 KB Output isn't correct
7 Incorrect 199 ms 43112 KB Output isn't correct
8 Correct 206 ms 47764 KB Output is correct
9 Incorrect 270 ms 50148 KB Output isn't correct
10 Incorrect 210 ms 51184 KB Output isn't correct
11 Incorrect 240 ms 52488 KB Output isn't correct
12 Incorrect 317 ms 52668 KB Output isn't correct
13 Correct 286 ms 58924 KB Output is correct
14 Incorrect 302 ms 58924 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 253 ms 58924 KB Output isn't correct
2 Incorrect 270 ms 58924 KB Output isn't correct
3 Correct 200 ms 63912 KB Output is correct
4 Incorrect 258 ms 63912 KB Output isn't correct
5 Incorrect 270 ms 63912 KB Output isn't correct
6 Incorrect 224 ms 64428 KB Output isn't correct
7 Incorrect 219 ms 64596 KB Output isn't correct
8 Correct 141 ms 70472 KB Output is correct
9 Incorrect 104 ms 70472 KB Output isn't correct