Submission #196843

#	Time	Username	Problem	Language	Result	Execution time	Memory
196843		dantoh000	Ball Machine (BOI13_ballmachine)	C++14	16.23 / 100	379 ms	20196 KiB

ballmachine

#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;
        //printf("testing %d %d %d\n",id[mid],sum(id[mid]),mid);
        if (sum(id[mid]) != mid) hi = mid;
        else lo = mid;
    }
    if (lo + 1 == hi){
        //printf("testing %d %d %d\n",id[lo],sum(id[lo]),lo);
        if (sum(id[lo]) != lo) hi = lo;
        else lo = hi;
    }
    up(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("added %d %d\n",i,last);
            }
            printf("%d\n",last);
        }
        else printf("%d\n",d[x]-d[rem(x)]);
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:85: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:87: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:96: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.8461538461538463 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 0 / 40
• Subtask 4: 1.6666666666666667 / 5