oj.uz

Submission #196882

# Submission time Handle Problem Language Result Execution time Memory
196882 2020-01-17T13:06:07 Z dantoh000 Ball Machine (BOI13_ballmachine) C++14
66.7277 / 100
 318 ms 23932 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n,q;
vector<int> adjlist[N];
int ct = 1;
int p[N][20];
int d[N], mn[N], l[N], r[N], pos[N];
int fw[N], id[N];
int root;
void up(int x, int v){
    while (x <= N){
        fw[x] += v;
        x += x&(-x);
    }
}
int sum(int x){
    int res = 0;
    while (x){
        res += fw[x];
        x -= x&(-x);
    }
    return res;
}
int sum(int s, int e){
    return sum(e)-sum(s-1);
}
void print(){ for (int i = 1; i <= n; i++) printf("%d ",sum(i,i)); printf("\n");}
void dfs(int u){
    mn[u] = u;
    for (auto v : adjlist[u]){
        d[v] = d[u]+1;
        for (int k = 1; k < 20; k++){
            p[v][k] = p[p[v][k-1]][k-1];
            if (p[v][k] == 0) break;
        }
        dfs(v);
        mn[u] = min(mn[u],mn[v]);
    }
    return;
}
void visit(int u){
    l[u] = ct;
    for (auto v : adjlist[u]){
        if (mn[v] == mn[u]) visit(v);
    }
    for (auto v : adjlist[u]){
        if (mn[v] != mn[u]) visit(v);
    }
    id[ct] = u;
    pos[u] = ct;
    r[u] = ct++;
}
int add(){
    int lo = 0, hi = n;
    while (lo + 1 < hi){
        int mid = (lo+hi)/2;
        if (sum(mid) != mid) hi = mid;
        else lo = mid;
    }
    up(lo+1,1);
    ///print();
    return id[lo+1];
}
int rem(int x){
    int ans = 0;
    for (int k = 19; k >= 0; k--){
        int P = p[x][k];
        if (P && sum(l[P],r[P]) == r[P]-l[P]+1){
            x = P;
            ans |= (1<<k);
        }
    }
    up(pos[x],-1);
    ///print();
    return ans;
}
int main(){
    scanf("%d%d",&n,&q);
    for (int i = 1; i <= n; i++){
        scanf("%d",&p[i][0]);
        if (p[i][0] == 0) root = i;
        else adjlist[p[i][0]].push_back(i);
    }
    dfs(root);
    visit(root);
    for (int i = 0; i < q; i++){
        int t,x;
        scanf("%d%d",&t,&x);
        if (t == 1){
            int last;
            while (x--){
                last = add();
                //printf("added %d %d\n",i,last);
            }
            printf("%d\n",last);
        }
        else {
            printf("%d\n",rem(x));
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:79: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:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[i][0]);
         ~~~~~^~~~~~~~~~~~~~~
ballmachine.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&t,&x);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
23.0769230769 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 142 ms 11512 KB Output is correct
3 Correct 78 ms 11516 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 5 ms 2940 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 6 ms 2936 KB Output is correct
9 Correct 13 ms 3320 KB Output is correct
10 Correct 30 ms 4984 KB Output is correct
11 Correct 166 ms 11640 KB Output is correct
12 Correct 79 ms 11512 KB Output is correct
13 Incorrect 142 ms 11540 KB Output isn't correct

Subtask #2
21.4285714286 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 6972 KB Output is correct
2 Correct 249 ms 19164 KB Output is correct
3 Correct 87 ms 15204 KB Output is correct
4 Incorrect 99 ms 8316 KB Output isn't correct
5 Incorrect 107 ms 8056 KB Output isn't correct
6 Correct 101 ms 8088 KB Output is correct
7 Incorrect 101 ms 7288 KB Output isn't correct
8 Correct 47 ms 6904 KB Output is correct
9 Incorrect 252 ms 19704 KB Output isn't correct
10 Correct 235 ms 19280 KB Output is correct
11 Correct 231 ms 18972 KB Output is correct
12 Correct 230 ms 17448 KB Output is correct
13 Correct 190 ms 21388 KB Output is correct
14 Correct 118 ms 15172 KB Output is correct

Subtask #3
20.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 11256 KB Output isn't correct
2 Incorrect 255 ms 17572 KB Output isn't correct
3 Correct 190 ms 19532 KB Output is correct
4 Incorrect 157 ms 16120 KB Output isn't correct
5 Correct 236 ms 15848 KB Output is correct
6 Correct 204 ms 15940 KB Output is correct
7 Incorrect 181 ms 14620 KB Output isn't correct
8 Correct 212 ms 19484 KB Output is correct
9 Incorrect 311 ms 19684 KB Output isn't correct
10 Correct 283 ms 19140 KB Output is correct
11 Correct 283 ms 19184 KB Output is correct
12 Incorrect 253 ms 17656 KB Output isn't correct
13 Correct 318 ms 23648 KB Output is correct
14 Incorrect 167 ms 15348 KB Output isn't correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 288 ms 19688 KB Output isn't correct
2 Incorrect 315 ms 17524 KB Output isn't correct
3 Correct 163 ms 23204 KB Output is correct
4 Incorrect 296 ms 19844 KB Output isn't correct
5 Correct 257 ms 19964 KB Output is correct
6 Incorrect 213 ms 19704 KB Output isn't correct
7 Incorrect 246 ms 18664 KB Output isn't correct
8 Correct 162 ms 23932 KB Output is correct
9 Correct 86 ms 15448 KB Output is correct