oj.uz

Submission #196845

# Submission time Handle Problem Language Result Execution time Memory
196845 2020-01-17T08:49:11 Z dantoh000 Ball Machine (BOI13_ballmachine) C++14
0 / 100
 217 ms 20768 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("0\n");
            //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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2808 KB Output isn't correct
2 Incorrect 111 ms 10488 KB Output isn't correct
3 Incorrect 92 ms 10748 KB Output isn't correct
4 Incorrect 4 ms 2684 KB Output isn't correct
5 Incorrect 4 ms 2680 KB Output isn't correct
6 Incorrect 5 ms 2808 KB Output isn't correct
7 Incorrect 6 ms 2808 KB Output isn't correct
8 Incorrect 6 ms 2836 KB Output isn't correct
9 Incorrect 10 ms 3192 KB Output isn't correct
10 Incorrect 22 ms 4600 KB Output isn't correct
11 Incorrect 89 ms 10488 KB Output isn't correct
12 Incorrect 68 ms 10616 KB Output isn't correct
13 Incorrect 86 ms 10488 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 6404 KB Output isn't correct
2 Incorrect 199 ms 17096 KB Output isn't correct
3 Incorrect 85 ms 14320 KB Output isn't correct
4 Incorrect 56 ms 7416 KB Output isn't correct
5 Incorrect 62 ms 7288 KB Output isn't correct
6 Incorrect 56 ms 7188 KB Output isn't correct
7 Incorrect 55 ms 6520 KB Output isn't correct
8 Incorrect 57 ms 6392 KB Output isn't correct
9 Incorrect 142 ms 17644 KB Output isn't correct
10 Incorrect 155 ms 17088 KB Output isn't correct
11 Incorrect 152 ms 17012 KB Output isn't correct
12 Incorrect 163 ms 15672 KB Output isn't correct
13 Incorrect 168 ms 18628 KB Output isn't correct
14 Incorrect 84 ms 14316 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 10200 KB Output isn't correct
2 Incorrect 140 ms 15860 KB Output isn't correct
3 Incorrect 115 ms 17008 KB Output isn't correct
4 Incorrect 102 ms 14500 KB Output isn't correct
5 Incorrect 106 ms 14192 KB Output isn't correct
6 Incorrect 109 ms 14192 KB Output isn't correct
7 Incorrect 104 ms 13296 KB Output isn't correct
8 Incorrect 120 ms 17016 KB Output isn't correct
9 Incorrect 141 ms 17520 KB Output isn't correct
10 Incorrect 156 ms 17136 KB Output isn't correct
11 Incorrect 170 ms 17112 KB Output isn't correct
12 Incorrect 158 ms 16076 KB Output isn't correct
13 Incorrect 217 ms 20736 KB Output isn't correct
14 Incorrect 96 ms 14320 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 17488 KB Output isn't correct
2 Incorrect 154 ms 15956 KB Output isn't correct
3 Incorrect 169 ms 20712 KB Output isn't correct
4 Incorrect 170 ms 17708 KB Output isn't correct
5 Incorrect 181 ms 17224 KB Output isn't correct
6 Incorrect 199 ms 17136 KB Output isn't correct
7 Incorrect 191 ms 15984 KB Output isn't correct
8 Incorrect 172 ms 20768 KB Output isn't correct
9 Incorrect 85 ms 14320 KB Output isn't correct