oj.uz

Submission #196841

# Submission time Handle Problem Language Result Execution time Memory
196841 2020-01-17T08:34:05 Z dantoh000 Ball Machine (BOI13_ballmachine) C++14
0 / 100
 353 ms 22392 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,x; 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 ",id[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("%d\n",last);
        }
        else printf("%d\n",d[x]-d[rem(x)]);
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:84:20: warning: unused variable 'x' [-Wunused-variable]
     for (int i = 1,x; i <= n; i++){
                    ^
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:97: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 2680 KB Output isn't correct
2 Incorrect 197 ms 11696 KB Output isn't correct
3 Incorrect 105 ms 11844 KB Output isn't correct
4 Incorrect 4 ms 2808 KB Output isn't correct
5 Incorrect 4 ms 2808 KB Output isn't correct
6 Incorrect 5 ms 2844 KB Output isn't correct
7 Incorrect 5 ms 2808 KB Output isn't correct
8 Incorrect 5 ms 2936 KB Output isn't correct
9 Incorrect 12 ms 3320 KB Output isn't correct
10 Incorrect 34 ms 4984 KB Output isn't correct
11 Incorrect 165 ms 11776 KB Output isn't correct
12 Incorrect 102 ms 11768 KB Output isn't correct
13 Incorrect 165 ms 11768 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 6944 KB Output isn't correct
2 Incorrect 350 ms 18724 KB Output isn't correct
3 Incorrect 114 ms 15472 KB Output isn't correct
4 Incorrect 134 ms 8136 KB Output isn't correct
5 Incorrect 170 ms 8056 KB Output isn't correct
6 Incorrect 159 ms 8112 KB Output isn't correct
7 Incorrect 144 ms 7532 KB Output isn't correct
8 Incorrect 70 ms 7032 KB Output isn't correct
9 Incorrect 285 ms 19368 KB Output isn't correct
10 Incorrect 346 ms 18676 KB Output isn't correct
11 Incorrect 318 ms 18716 KB Output isn't correct
12 Incorrect 278 ms 17516 KB Output isn't correct
13 Incorrect 185 ms 20080 KB Output isn't correct
14 Incorrect 116 ms 15472 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 10996 KB Output isn't correct
2 Incorrect 353 ms 17592 KB Output isn't correct
3 Incorrect 273 ms 18416 KB Output isn't correct
4 Incorrect 187 ms 15716 KB Output isn't correct
5 Incorrect 286 ms 15348 KB Output isn't correct
6 Incorrect 267 ms 15548 KB Output isn't correct
7 Incorrect 244 ms 14452 KB Output isn't correct
8 Incorrect 218 ms 18288 KB Output isn't correct
9 Incorrect 274 ms 19108 KB Output isn't correct
10 Incorrect 340 ms 18688 KB Output isn't correct
11 Incorrect 343 ms 18712 KB Output isn't correct
12 Incorrect 319 ms 17548 KB Output isn't correct
13 Incorrect 336 ms 22076 KB Output isn't correct
14 Incorrect 176 ms 15884 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 324 ms 19128 KB Output isn't correct
2 Incorrect 333 ms 17520 KB Output isn't correct
3 Incorrect 205 ms 22260 KB Output isn't correct
4 Incorrect 317 ms 19056 KB Output isn't correct
5 Incorrect 346 ms 18864 KB Output isn't correct
6 Incorrect 302 ms 18992 KB Output isn't correct
7 Incorrect 327 ms 17688 KB Output isn't correct
8 Incorrect 206 ms 22392 KB Output isn't correct
9 Incorrect 113 ms 15348 KB Output isn't correct