oj.uz

Submission #196842

# Submission time Handle Problem Language Result Execution time Memory
196842 2020-01-17T08:35:04 Z dantoh000 Ball Machine (BOI13_ballmachine) C++14
0 / 100
 389 ms 20592 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];
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 (isempty(id[mid])) hi = mid;
        else lo = mid;
    }
    if (lo + 1 == hi){
        if (isempty(id[lo])) hi = lo;
        else lo = hi;
    }
    up(l[id[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(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 = 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("%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:94: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 4 ms 2808 KB Output isn't correct
2 Incorrect 161 ms 10232 KB Output isn't correct
3 Incorrect 95 ms 10356 KB Output isn't correct
4 Incorrect 4 ms 2680 KB Output isn't correct
5 Incorrect 4 ms 2680 KB Output isn't correct
6 Incorrect 5 ms 2812 KB Output isn't correct
7 Incorrect 11 ms 2808 KB Output isn't correct
8 Incorrect 5 ms 2808 KB Output isn't correct
9 Incorrect 11 ms 3192 KB Output isn't correct
10 Incorrect 33 ms 4600 KB Output isn't correct
11 Incorrect 156 ms 10120 KB Output isn't correct
12 Incorrect 96 ms 10440 KB Output isn't correct
13 Incorrect 126 ms 10232 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 6392 KB Output isn't correct
2 Incorrect 328 ms 16752 KB Output isn't correct
3 Incorrect 106 ms 13940 KB Output isn't correct
4 Incorrect 131 ms 7368 KB Output isn't correct
5 Incorrect 156 ms 7168 KB Output isn't correct
6 Incorrect 146 ms 7132 KB Output isn't correct
7 Incorrect 141 ms 6448 KB Output isn't correct
8 Incorrect 68 ms 6392 KB Output isn't correct
9 Incorrect 278 ms 17392 KB Output isn't correct
10 Incorrect 336 ms 16760 KB Output isn't correct
11 Incorrect 389 ms 16732 KB Output isn't correct
12 Incorrect 349 ms 15728 KB Output isn't correct
13 Incorrect 184 ms 18492 KB Output isn't correct
14 Incorrect 106 ms 13944 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 9976 KB Output isn't correct
2 Incorrect 368 ms 15632 KB Output isn't correct
3 Incorrect 214 ms 16880 KB Output isn't correct
4 Incorrect 194 ms 14212 KB Output isn't correct
5 Incorrect 218 ms 14016 KB Output isn't correct
6 Incorrect 222 ms 13940 KB Output isn't correct
7 Incorrect 239 ms 12964 KB Output isn't correct
8 Incorrect 219 ms 16704 KB Output isn't correct
9 Incorrect 261 ms 17136 KB Output isn't correct
10 Incorrect 346 ms 16892 KB Output isn't correct
11 Incorrect 337 ms 16884 KB Output isn't correct
12 Incorrect 335 ms 15860 KB Output isn't correct
13 Incorrect 333 ms 20356 KB Output isn't correct
14 Incorrect 168 ms 13932 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 387 ms 17176 KB Output isn't correct
2 Incorrect 313 ms 15472 KB Output isn't correct
3 Incorrect 198 ms 20464 KB Output isn't correct
4 Incorrect 304 ms 17252 KB Output isn't correct
5 Incorrect 346 ms 16736 KB Output isn't correct
6 Incorrect 296 ms 17008 KB Output isn't correct
7 Incorrect 345 ms 15600 KB Output isn't correct
8 Incorrect 228 ms 20592 KB Output isn't correct
9 Incorrect 95 ms 13808 KB Output isn't correct