Submission #196849

#	Time	Username	Problem	Language	Result	Execution time	Memory
196849		dantoh000	Ball Machine (BOI13_ballmachine)	C++14	66.73 / 100	335 ms	21108 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][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 isfull(int x) {
    //printf("check %d, %d %d ,%d = %d?\n",x,l[x],r[x],sum(l[x],r[x]),sz[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 (sum(mid) != mid) hi = mid;
        else lo = mid;
    }
    if (lo + 1 == hi){
        if (sum(lo) != lo) hi = lo;
        else lo = hi;
    }
    up(lo,1);
    /*for (int i = 1; i<= n; i++){
        printf("%d ",sum(i,i));
    }
    printf("\n");*/
    return id[lo];
}
int rem(int x){
    int ans = 0;
    for (int k = 16; k >= 0; k--){
        if (p[x][k] && isfull(p[x][k])){
            x = p[x][k];
            ans ^= (1<<k);
        }
    }
    //printf("top most %d\n",x);
    up(pos[x],-1);
    /*for (int i = 1; i<= n; i++){
        printf("%d ",sum(i,i));
    }
    printf("\n");*/
    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;
        adjlist[p[i][0]].push_back(i);
    }
    id.push_back(0);
    dfs(root);
    visit(root);
    for (int i = 1; i <= n; i++) {
        //printf("%d ",i);
        pos[id[i]] = 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("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:95: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:97: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:110: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.076923076923077 / 25
• Subtask 2: 21.428571428571427 / 30
• Subtask 3: 20 / 40
• Subtask 4: 2.2222222222222223 / 5