oj.uz

Submission #55471

# Submission time Handle Problem Language Result Execution time Memory
55471 2018-07-07T15:47:56 Z Diuven Ball Machine (BOI13_ballmachine) C++11
7.53968 / 100
 267 ms 24752 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;
    // cout<<"PLACED: "<<v<<'\n';
    return v;
}

int pop(int v){
    S.insert(nu[v]);
    B[v]=false;
    return 0;
    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 5 ms 2680 KB Output isn't correct
2 Incorrect 138 ms 12684 KB Output isn't correct
3 Incorrect 115 ms 13068 KB Output isn't correct
4 Incorrect 5 ms 13068 KB Output isn't correct
5 Incorrect 4 ms 13068 KB Output isn't correct
6 Incorrect 6 ms 13068 KB Output isn't correct
7 Incorrect 4 ms 13068 KB Output isn't correct
8 Incorrect 5 ms 13068 KB Output isn't correct
9 Incorrect 12 ms 13068 KB Output isn't correct
10 Incorrect 32 ms 13068 KB Output isn't correct
11 Incorrect 169 ms 13068 KB Output isn't correct
12 Incorrect 109 ms 13208 KB Output isn't correct
13 Incorrect 104 ms 13208 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13208 KB Output is correct
2 Incorrect 254 ms 20864 KB Output isn't correct
3 Incorrect 116 ms 20864 KB Output isn't correct
4 Incorrect 114 ms 20864 KB Output isn't correct
5 Incorrect 136 ms 20864 KB Output isn't correct
6 Incorrect 108 ms 20864 KB Output isn't correct
7 Incorrect 94 ms 20864 KB Output isn't correct
8 Correct 46 ms 20864 KB Output is correct
9 Incorrect 204 ms 21432 KB Output isn't correct
10 Incorrect 251 ms 21432 KB Output isn't correct
11 Incorrect 232 ms 21432 KB Output isn't correct
12 Incorrect 230 ms 21432 KB Output isn't correct
13 Correct 137 ms 22076 KB Output is correct
14 Incorrect 117 ms 22076 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 22076 KB Output isn't correct
2 Incorrect 218 ms 22076 KB Output isn't correct
3 Incorrect 183 ms 22076 KB Output isn't correct
4 Incorrect 147 ms 22076 KB Output isn't correct
5 Incorrect 170 ms 22076 KB Output isn't correct
6 Incorrect 181 ms 22076 KB Output isn't correct
7 Incorrect 139 ms 22076 KB Output isn't correct
8 Incorrect 163 ms 22076 KB Output isn't correct
9 Incorrect 248 ms 22076 KB Output isn't correct
10 Incorrect 197 ms 22076 KB Output isn't correct
11 Incorrect 246 ms 22076 KB Output isn't correct
12 Incorrect 255 ms 22076 KB Output isn't correct
13 Incorrect 246 ms 24380 KB Output isn't correct
14 Incorrect 238 ms 24380 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 228 ms 24380 KB Output isn't correct
2 Incorrect 267 ms 24380 KB Output isn't correct
3 Correct 219 ms 24548 KB Output is correct
4 Incorrect 220 ms 24548 KB Output isn't correct
5 Incorrect 236 ms 24548 KB Output isn't correct
6 Incorrect 202 ms 24548 KB Output isn't correct
7 Incorrect 240 ms 24548 KB Output isn't correct
8 Correct 187 ms 24752 KB Output is correct
9 Incorrect 175 ms 24752 KB Output isn't correct