oj.uz

Submission #196855

# Submission time Handle Problem Language Result Execution time Memory
196855 2020-01-17T09:58:23 Z dantoh000 Ball Machine (BOI13_ballmachine) C++14
66.7277 / 100
 338 ms 23928 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][18];
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 < 18; 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 = 1, hi = n;
    while (lo + 1 < hi){
        int mid = (lo+hi)/2;
        if (sum(mid) != mid) hi = mid;
        else lo = mid;
    }
    if (lo + 1 == hi){
        if (sum(lo) != lo) hi = lo;
        else lo = hi;
    }
    up(lo,1);
    ///print();
    return id[lo];
}
int rem(int x){
    int ans = 0;
    for (int k = 17; 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;
        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;
            for (int i = 0; i < x; i++){
                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:83: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:85: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:93: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 133 ms 11720 KB Output is correct
3 Correct 73 ms 11256 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 7 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 5 ms 2936 KB Output is correct
9 Correct 12 ms 3320 KB Output is correct
10 Correct 29 ms 4856 KB Output is correct
11 Correct 135 ms 11484 KB Output is correct
12 Correct 74 ms 11256 KB Output is correct
13 Incorrect 119 ms 11224 KB Output isn't correct

Subtask #2
21.4285714286 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7004 KB Output is correct
2 Correct 253 ms 18956 KB Output is correct
3 Correct 89 ms 14700 KB Output is correct
4 Incorrect 110 ms 8328 KB Output isn't correct
5 Incorrect 116 ms 8056 KB Output isn't correct
6 Correct 102 ms 8028 KB Output is correct
7 Incorrect 107 ms 7300 KB Output isn't correct
8 Correct 55 ms 6904 KB Output is correct
9 Incorrect 266 ms 19320 KB Output isn't correct
10 Correct 320 ms 18948 KB Output is correct
11 Correct 295 ms 18900 KB Output is correct
12 Correct 318 ms 17156 KB Output is correct
13 Correct 198 ms 20860 KB Output is correct
14 Correct 84 ms 14580 KB Output is correct

Subtask #3
20.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 11256 KB Output isn't correct
2 Incorrect 256 ms 17652 KB Output isn't correct
3 Correct 184 ms 19320 KB Output is correct
4 Incorrect 170 ms 16092 KB Output isn't correct
5 Correct 153 ms 15560 KB Output is correct
6 Correct 230 ms 15748 KB Output is correct
7 Incorrect 229 ms 14584 KB Output isn't correct
8 Correct 245 ms 19252 KB Output is correct
9 Incorrect 306 ms 19832 KB Output isn't correct
10 Correct 338 ms 19320 KB Output is correct
11 Correct 252 ms 19320 KB Output is correct
12 Incorrect 255 ms 17732 KB Output isn't correct
13 Correct 278 ms 23928 KB Output is correct
14 Incorrect 178 ms 15408 KB Output isn't correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 247 ms 19580 KB Output isn't correct
2 Incorrect 325 ms 17516 KB Output isn't correct
3 Correct 213 ms 23032 KB Output is correct
4 Incorrect 330 ms 19704 KB Output isn't correct
5 Correct 324 ms 19184 KB Output is correct
6 Incorrect 223 ms 18880 KB Output isn't correct
7 Incorrect 275 ms 17784 KB Output isn't correct
8 Correct 222 ms 23032 KB Output is correct
9 Correct 105 ms 14580 KB Output is correct