Submission #1094976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094976		Sunbae	Ball Machine (BOI13_ballmachine)	C++17	24.80 / 100	211 ms	22352 KiB

ballmachine

#include <bits/stdc++.h>
#define z exit(0)
using namespace std;
const int N = 1e5 + 5;
vector<int> g[N];
int mn[N], E[N], dep[N], SZ[N], T[N], up[N][17], LOG, sz, m;
void dfs(int u){
    mn[u] = u;
    for(int j = 1; j<LOG; ++j) up[u][j] = up[up[u][j-1]][j-1];
    for(int v: g[u]) dfs(v), mn[u] = min(mn[u], mn[v]);
}
bool cmp(int u, int v){ return mn[u] < mn[v];}
void efs(int u){ 
    sort(g[u].begin(), g[u].end(), cmp);
    for(int v: g[u]) dep[v] = dep[u] + 1, efs(v);
    E[m++] = u;
}
inline int kth_anc(int u, int k){
    for(int j = LOG-1; j>=0; --j) if(k>>j&1) u = up[u][j]; return u;
}
signed main(){
    int n, q, rt; scanf("%d %d", &n, &q); LOG = 32 - __builtin_clz(n);
    for(int v = 0, u; v<n; ++v){
        scanf("%d", &u); 
        if(--u >= 0) g[up[v][0] = u].push_back(v);
        else rt = v;
    }
    up[rt][0] = rt;
    dfs(rt); efs(rt);
    for(int i = 0; i<n; ++i) SZ[E[i]] = i+1, T[i+1] = E[i];
    for(int i = 0, op, k, u; i<q; ++i){
        scanf("%d", &op);
        if(op == 1){
            scanf("%d", &k);
            printf("%d\n", T[sz+=k] + 1);
        }else{
            scanf("%d", &u); --u;
            if(u == rt || sz < SZ[up[u][0]]){ puts("0"); --sz; continue;}
            int low = 1, high = dep[u], v = u;
            while(low <= high){
                int mid = low + ((high-low)>>1), anc = kth_anc(u, mid);
                if(sz >= SZ[anc]) low = mid+1, v = anc;
                else high = mid-1;
            }
            printf("%d\n", dep[u] - dep[v]); --sz;
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int kth_anc(int, int)':
ballmachine.cpp:19:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   19 |     for(int j = LOG-1; j>=0; --j) if(k>>j&1) u = up[u][j]; return u;
      |     ^~~
ballmachine.cpp:19:60: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   19 |     for(int j = LOG-1; j>=0; --j) if(k>>j&1) u = up[u][j]; return u;
      |                                                            ^~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:22:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     int n, q, rt; scanf("%d %d", &n, &q); LOG = 32 - __builtin_clz(n);
      |                   ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%d", &u);
      |         ~~~~~^~~~~~~~~~
ballmachine.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d", &op);
      |         ~~~~~^~~~~~~~~~~
ballmachine.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |             scanf("%d", &k);
      |             ~~~~~^~~~~~~~~~
ballmachine.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |             scanf("%d", &u); --u;
      |             ~~~~~^~~~~~~~~~
ballmachine.cpp:38:13: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |             if(u == rt || sz < SZ[up[u][0]]){ puts("0"); --sz; continue;}
      |             ^~

• Subtask 1: 3.8461538461538463 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 8.571428571428571 / 40
• Subtask 4: 1.6666666666666667 / 5