oj.uz

Submission #196844

# Submission time Handle Problem Language Result Execution time Memory
196844 2020-01-17T08:48:07 Z dantoh000 Ball Machine (BOI13_ballmachine) C++14
20.5128 / 100
 353 ms 20596 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n,q;
vector<int> adjlist[N];
int ct = 0;
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 isempty(int 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);
    return id[hi];
}
int rem(int x){
    for (int k = 16; k >= 0; k--){
        if (p[x][k] && !isempty(p[x][k])){
            x = p[x][k];
        }
    }
    up(pos[x],-1);
    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: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:98: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
3.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2808 KB Output isn't correct
2 Incorrect 157 ms 10488 KB Output isn't correct
3 Correct 98 ms 10616 KB Output is correct
4 Incorrect 4 ms 2680 KB Output isn't correct
5 Incorrect 4 ms 2808 KB Output isn't correct
6 Incorrect 5 ms 2808 KB Output isn't correct
7 Incorrect 5 ms 2808 KB Output isn't correct
8 Incorrect 3 ms 2808 KB Output isn't correct
9 Incorrect 11 ms 3192 KB Output isn't correct
10 Incorrect 28 ms 4728 KB Output isn't correct
11 Incorrect 129 ms 10520 KB Output isn't correct
12 Correct 75 ms 10620 KB Output is correct
13 Incorrect 109 ms 10204 KB Output isn't correct

Subtask #2
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 6372 KB Output is correct
2 Incorrect 273 ms 16948 KB Output isn't correct
3 Correct 86 ms 13904 KB Output is correct
4 Incorrect 101 ms 7392 KB Output isn't correct
5 Incorrect 149 ms 7416 KB Output isn't correct
6 Correct 126 ms 7160 KB Output is correct
7 Incorrect 127 ms 6644 KB Output isn't correct
8 Correct 57 ms 6300 KB Output is correct
9 Incorrect 284 ms 17468 KB Output isn't correct
10 Incorrect 353 ms 17024 KB Output isn't correct
11 Correct 251 ms 16756 KB Output is correct
12 Incorrect 250 ms 15472 KB Output isn't correct
13 Correct 163 ms 18524 KB Output is correct
14 Correct 85 ms 13936 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 10300 KB Output isn't correct
2 Incorrect 264 ms 15964 KB Output isn't correct
3 Incorrect 167 ms 16948 KB Output isn't correct
4 Incorrect 146 ms 14444 KB Output isn't correct
5 Incorrect 187 ms 14340 KB Output isn't correct
6 Incorrect 174 ms 14124 KB Output isn't correct
7 Incorrect 172 ms 13184 KB Output isn't correct
8 Incorrect 169 ms 17008 KB Output isn't correct
9 Incorrect 209 ms 17512 KB Output isn't correct
10 Incorrect 305 ms 17140 KB Output isn't correct
11 Incorrect 302 ms 17192 KB Output isn't correct
12 Incorrect 319 ms 16008 KB Output isn't correct
13 Incorrect 276 ms 20596 KB Output isn't correct
14 Incorrect 127 ms 14320 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 301 ms 17392 KB Output isn't correct
2 Incorrect 327 ms 15980 KB Output isn't correct
3 Correct 220 ms 20472 KB Output is correct
4 Incorrect 296 ms 17356 KB Output isn't correct
5 Incorrect 345 ms 17056 KB Output isn't correct
6 Incorrect 300 ms 16740 KB Output isn't correct
7 Incorrect 334 ms 16000 KB Output isn't correct
8 Correct 251 ms 20468 KB Output is correct
9 Correct 105 ms 13936 KB Output is correct