oj.uz

Submission #196879

# Submission time Handle Problem Language Result Execution time Memory
196879 2020-01-17T13:03:31 Z dantoh000 Ball Machine (BOI13_ballmachine) C++14
35.5006 / 100
 280 ms 24368 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];
            //printf("%d p=%d %d\n",v,k,p[v][k]);
            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 = 1, hi = n;
    while (lo + 1 < hi){
        int mid = (lo+hi)/2;
        if (sum(mid) == mid) lo = mid;
        else hi = 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];
        //printf("%d %d %d\n",x,k,P);
        if (P && sum(l[P],r[P]) == r[P]-l[P]+1){
            x = P;
            ans |= (1<<k);
        }
    }
    //printf("remove %d ",x);
    up(pos[x],-1);
    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:81: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:83: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:91: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
19.2307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2812 KB Output is correct
2 Correct 134 ms 12028 KB Output is correct
3 Incorrect 74 ms 11764 KB Output isn't correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 2728 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct
7 Correct 6 ms 2936 KB Output is correct
8 Correct 7 ms 2964 KB Output is correct
9 Correct 12 ms 3320 KB Output is correct
10 Correct 33 ms 5024 KB Output is correct
11 Correct 173 ms 11896 KB Output is correct
12 Incorrect 77 ms 11768 KB Output isn't correct
13 Incorrect 117 ms 11768 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 7132 KB Output isn't correct
2 Incorrect 251 ms 19776 KB Output isn't correct
3 Incorrect 85 ms 15604 KB Output isn't correct
4 Incorrect 103 ms 8568 KB Output isn't correct
5 Incorrect 107 ms 8312 KB Output isn't correct
6 Correct 99 ms 8284 KB Output is correct
7 Incorrect 110 ms 7548 KB Output isn't correct
8 Incorrect 47 ms 7160 KB Output isn't correct
9 Incorrect 199 ms 20156 KB Output isn't correct
10 Incorrect 233 ms 19704 KB Output isn't correct
11 Correct 218 ms 19576 KB Output is correct
12 Incorrect 208 ms 17824 KB Output isn't correct
13 Incorrect 144 ms 21496 KB Output isn't correct
14 Incorrect 85 ms 15560 KB Output isn't correct

Subtask #3
11.4285714286 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 11656 KB Output isn't correct
2 Incorrect 255 ms 18476 KB Output isn't correct
3 Correct 179 ms 19932 KB Output is correct
4 Incorrect 156 ms 16704 KB Output isn't correct
5 Incorrect 166 ms 16268 KB Output isn't correct
6 Incorrect 161 ms 16176 KB Output isn't correct
7 Incorrect 185 ms 15228 KB Output isn't correct
8 Correct 176 ms 19820 KB Output is correct
9 Incorrect 246 ms 20500 KB Output isn't correct
10 Correct 258 ms 20176 KB Output is correct
11 Incorrect 250 ms 19960 KB Output isn't correct
12 Incorrect 245 ms 18328 KB Output isn't correct
13 Correct 280 ms 24368 KB Output is correct
14 Incorrect 139 ms 15988 KB Output isn't correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 253 ms 20388 KB Output isn't correct
2 Incorrect 243 ms 18248 KB Output isn't correct
3 Incorrect 158 ms 23800 KB Output isn't correct
4 Incorrect 256 ms 20088 KB Output isn't correct
5 Correct 253 ms 19576 KB Output is correct
6 Incorrect 211 ms 19320 KB Output isn't correct
7 Incorrect 239 ms 18048 KB Output isn't correct
8 Incorrect 165 ms 23756 KB Output isn't correct
9 Incorrect 87 ms 15692 KB Output isn't correct