Submission #196860

#	Time	Username	Problem	Language	Result	Execution time	Memory
196860		dantoh000	Ball Machine (BOI13_ballmachine)	C++14	62.88 / 100	365 ms	23672 KiB

ballmachine

#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);
    }
    p[root][0] = root;
    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 (stderr)

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: 19.23076923076923 / 25
• Subtask 2: 21.428571428571427 / 30
• Subtask 3: 20 / 40
• Subtask 4: 2.2222222222222223 / 5