oj.uz

Submission #196846

# Submission time Handle Problem Language Result Execution time Memory
196846 2020-01-17T08:58:36 Z dantoh000 Ball Machine (BOI13_ballmachine) C++14
66.7277 / 100
 344 ms 21080 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][17];
int d[N];
int sz[N], mn[N], l[N], r[N],pos[N];
int fw[N];
vector<int> id;
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 dfs(int u){
    sz[u] = 1;
    mn[u] = u;
    for (auto v : adjlist[u]){
        d[v] = d[u]+1;
        for (int k = 1; k < 17; k++){
            p[v][k] = p[p[v][k-1]][k-1];
            if (p[v][k] == 0) break;
        }
        dfs(v);
        sz[u] += sz[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.push_back(u);
    r[u] = ct++;
}
bool isfull(int x) {
    //printf("%d %d ,%d = %d?\n",l[x],r[x],sum(l[x],r[x]),sz[x]);
    return sum(l[x],r[x]) == sz[x];
}
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(hi,1);
    /*for (int i = 1; i<= n; i++){
        printf("%d ",sum(i,i));
    }
    printf("\n");*/
    return id[hi];
}
int rem(int x){
    for (int k = 16; k >= 0; k--){
        if (p[x][k] && isfull(p[x][k])){
            x = p[x][k];
        }
    }
    //printf("top most %d\n",x);
    up(pos[x],-1);
    /*for (int i = 1; i<= n; i++){
        printf("%d ",sum(i,i));
    }
    printf("\n");*/
    return x;
}
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);
    }
    id.push_back(0);
    dfs(root);
    visit(root);
    for (int i = 1; i <= n; i++) {
        //printf("%d ",i);
        pos[id[i]] = i;
    }
    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",d[x]-d[rem(x)]);
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:93: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:95: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:108: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 2680 KB Output is correct
2 Correct 137 ms 10420 KB Output is correct
3 Correct 75 ms 10488 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 11 ms 3192 KB Output is correct
10 Correct 29 ms 4728 KB Output is correct
11 Correct 137 ms 10392 KB Output is correct
12 Correct 78 ms 10488 KB Output is correct
13 Incorrect 115 ms 10232 KB Output isn't correct

Subtask #2
21.4285714286 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6316 KB Output is correct
2 Correct 246 ms 17296 KB Output is correct
3 Correct 86 ms 13936 KB Output is correct
4 Incorrect 102 ms 7288 KB Output isn't correct
5 Incorrect 110 ms 7160 KB Output isn't correct
6 Correct 103 ms 7296 KB Output is correct
7 Incorrect 106 ms 6520 KB Output isn't correct
8 Correct 51 ms 6356 KB Output is correct
9 Incorrect 204 ms 17392 KB Output isn't correct
10 Correct 246 ms 16900 KB Output is correct
11 Correct 241 ms 16908 KB Output is correct
12 Correct 256 ms 15456 KB Output is correct
13 Correct 139 ms 18416 KB Output is correct
14 Correct 102 ms 13908 KB Output is correct

Subtask #3
20.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 10244 KB Output isn't correct
2 Incorrect 324 ms 16084 KB Output isn't correct
3 Correct 249 ms 17200 KB Output is correct
4 Incorrect 201 ms 14700 KB Output isn't correct
5 Correct 222 ms 14196 KB Output is correct
6 Correct 164 ms 14196 KB Output is correct
7 Incorrect 219 ms 13360 KB Output isn't correct
8 Correct 225 ms 17352 KB Output is correct
9 Incorrect 326 ms 17872 KB Output isn't correct
10 Correct 344 ms 17264 KB Output is correct
11 Correct 340 ms 17284 KB Output is correct
12 Incorrect 308 ms 16244 KB Output isn't correct
13 Correct 325 ms 21080 KB Output is correct
14 Incorrect 160 ms 14328 KB Output isn't correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 329 ms 17752 KB Output isn't correct
2 Incorrect 314 ms 16148 KB Output isn't correct
3 Correct 159 ms 20508 KB Output is correct
4 Incorrect 274 ms 17724 KB Output isn't correct
5 Correct 317 ms 17160 KB Output is correct
6 Incorrect 227 ms 16880 KB Output isn't correct
7 Incorrect 249 ms 15984 KB Output isn't correct
8 Correct 155 ms 20504 KB Output is correct
9 Correct 86 ms 13936 KB Output is correct