Submission #1094974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094974		Sunbae	Ball Machine (BOI13_ballmachine)	C++17	24.80 / 100	90 ms	22608 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;
}
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 v = u;
            for(int j = LOG-1; j>=0; --j) if(sz >= SZ[up[v][j]]) v = up[v][j];
            printf("%d\n", dep[u] - dep[v]); --sz;
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:19:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     int n, q, rt; scanf("%d %d", &n, &q); LOG = 32 - __builtin_clz(n);
      |                   ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d", &u);
      |         ~~~~~^~~~~~~~~~
ballmachine.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d", &op);
      |         ~~~~~^~~~~~~~~~~
ballmachine.cpp:31:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |             scanf("%d", &k);
      |             ~~~~~^~~~~~~~~~
ballmachine.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |             scanf("%d", &u); --u;
      |             ~~~~~^~~~~~~~~~
ballmachine.cpp:35:13: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |             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