oj.uz

Submission #196848

# Submission time Handle Problem Language Result Execution time Memory
196848 2020-01-17T09:04:41 Z dantoh000 Ball Machine (BOI13_ballmachine) C++14
66.7277 / 100
 348 ms 21096 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("check %d, %d %d ,%d = %d?\n",x,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(lo,1);
    /*for (int i = 1; i<= n; i++){
        printf("%d ",sum(i,i));
    }
    printf("\n");*/
    return id[lo];
}
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 5 ms 2936 KB Output is correct
2 Correct 133 ms 11568 KB Output is correct
3 Correct 75 ms 11436 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2812 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 3320 KB Output is correct
10 Correct 26 ms 4856 KB Output is correct
11 Correct 132 ms 11544 KB Output is correct
12 Correct 76 ms 11384 KB Output is correct
13 Incorrect 124 ms 11364 KB Output isn't correct

Subtask #2
21.4285714286 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6768 KB Output is correct
2 Correct 255 ms 18256 KB Output is correct
3 Correct 86 ms 14832 KB Output is correct
4 Incorrect 107 ms 8156 KB Output isn't correct
5 Incorrect 129 ms 7928 KB Output isn't correct
6 Correct 102 ms 7868 KB Output is correct
7 Incorrect 100 ms 7288 KB Output isn't correct
8 Correct 35 ms 6820 KB Output is correct
9 Incorrect 199 ms 18800 KB Output isn't correct
10 Correct 251 ms 18288 KB Output is correct
11 Correct 223 ms 18160 KB Output is correct
12 Correct 238 ms 16908 KB Output is correct
13 Correct 147 ms 19680 KB Output is correct
14 Correct 88 ms 14816 KB Output is correct

Subtask #3
20.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 10860 KB Output isn't correct
2 Incorrect 274 ms 17584 KB Output isn't correct
3 Correct 192 ms 18216 KB Output is correct
4 Incorrect 184 ms 15620 KB Output isn't correct
5 Correct 180 ms 15184 KB Output is correct
6 Correct 171 ms 15152 KB Output is correct
7 Incorrect 159 ms 14204 KB Output isn't correct
8 Correct 187 ms 18032 KB Output is correct
9 Incorrect 248 ms 19056 KB Output isn't correct
10 Correct 272 ms 18568 KB Output is correct
11 Correct 270 ms 18548 KB Output is correct
12 Incorrect 279 ms 16092 KB Output isn't correct
13 Correct 329 ms 21096 KB Output is correct
14 Incorrect 138 ms 14324 KB Output isn't correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 265 ms 17708 KB Output isn't correct
2 Incorrect 255 ms 15984 KB Output isn't correct
3 Correct 161 ms 20524 KB Output is correct
4 Incorrect 271 ms 17752 KB Output isn't correct
5 Correct 348 ms 17140 KB Output is correct
6 Incorrect 227 ms 16880 KB Output isn't correct
7 Incorrect 253 ms 15984 KB Output isn't correct
8 Correct 157 ms 20468 KB Output is correct
9 Correct 86 ms 13936 KB Output is correct