oj.uz

Submission #196880

# Submission time Handle Problem Language Result Execution time Memory
196880 2020-01-17T13:04:53 Z dantoh000 Ball Machine (BOI13_ballmachine) C++14
66.7277 / 100
 343 ms 23424 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][20];
int d[N], mn[N], l[N], r[N], pos[N];
int fw[N], id[N];
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 print(){ for (int i = 1; i <= n; i++) printf("%d ",sum(i,i)); printf("\n");}
void dfs(int u){
    mn[u] = u;
    for (auto v : adjlist[u]){
        d[v] = d[u]+1;
        for (int k = 1; k < 20; k++){
            p[v][k] = p[p[v][k-1]][k-1];
            if (p[v][k] == 0) break;
        }
        dfs(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[ct] = u;
    pos[u] = ct;
    r[u] = ct++;
}
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);
    ///print();
    return id[lo];
}
int rem(int x){
    int ans = 0;
    for (int k = 19; k >= 0; k--){
        int P = p[x][k];
        if (P && sum(l[P],r[P]) == r[P]-l[P]+1){
            x = P;
            ans |= (1<<k);
        }
    }
    up(pos[x],-1);
    ///print();
    return ans;
}
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;
        else adjlist[p[i][0]].push_back(i);
    }
    dfs(root);
    visit(root);
    for (int i = 0; i < q; i++){
        int t,x;
        scanf("%d%d",&t,&x);
        if (t == 1){
            int last;
            while (x--){
                last = add();
                //printf("added %d %d\n",i,last);
            }
            printf("%d\n",last);
        }
        else {
            printf("%d\n",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:93: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 0 ms 2808 KB Output is correct
2 Correct 176 ms 11000 KB Output is correct
3 Correct 75 ms 10920 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 6 ms 2808 KB Output is correct
9 Correct 13 ms 3320 KB Output is correct
10 Correct 29 ms 4856 KB Output is correct
11 Correct 140 ms 10972 KB Output is correct
12 Correct 78 ms 10972 KB Output is correct
13 Incorrect 121 ms 10832 KB Output isn't correct

Subtask #2
21.4285714286 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6648 KB Output is correct
2 Correct 252 ms 18424 KB Output is correct
3 Correct 87 ms 14580 KB Output is correct
4 Incorrect 103 ms 7844 KB Output isn't correct
5 Incorrect 105 ms 7724 KB Output isn't correct
6 Correct 105 ms 7544 KB Output is correct
7 Incorrect 103 ms 6848 KB Output isn't correct
8 Correct 46 ms 6648 KB Output is correct
9 Incorrect 218 ms 18956 KB Output isn't correct
10 Correct 288 ms 18680 KB Output is correct
11 Correct 343 ms 18296 KB Output is correct
12 Correct 234 ms 16732 KB Output is correct
13 Correct 150 ms 20472 KB Output is correct
14 Correct 82 ms 14588 KB Output is correct

Subtask #3
20.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 11016 KB Output isn't correct
2 Incorrect 241 ms 17268 KB Output isn't correct
3 Correct 210 ms 19152 KB Output is correct
4 Incorrect 167 ms 15992 KB Output isn't correct
5 Correct 167 ms 15480 KB Output is correct
6 Correct 170 ms 15520 KB Output is correct
7 Incorrect 164 ms 14316 KB Output isn't correct
8 Correct 189 ms 19012 KB Output is correct
9 Incorrect 243 ms 19384 KB Output isn't correct
10 Correct 262 ms 19024 KB Output is correct
11 Correct 304 ms 18832 KB Output is correct
12 Incorrect 265 ms 17272 KB Output isn't correct
13 Correct 307 ms 23424 KB Output is correct
14 Incorrect 141 ms 14836 KB Output isn't correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 253 ms 19076 KB Output isn't correct
2 Incorrect 264 ms 17152 KB Output isn't correct
3 Correct 160 ms 22728 KB Output is correct
4 Incorrect 254 ms 19960 KB Output isn't correct
5 Correct 274 ms 19372 KB Output is correct
6 Incorrect 221 ms 19064 KB Output isn't correct
7 Incorrect 255 ms 17900 KB Output isn't correct
8 Correct 161 ms 23416 KB Output is correct
9 Correct 85 ms 15092 KB Output is correct