Submission #1094984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094984		Sunbae	Ball Machine (BOI13_ballmachine)	C++17	24.80 / 100	94 ms	21076 KiB

ballmachine

#include <bits/stdc++.h>
#define z exit(0)
using namespace std;
const int N = 1e5 + 5;
vector<int> g[N];
int up[N][17], dep[N], SZ[N], mn[N], T[N], E[N], LOG, m, sz;
void dfs(int 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 i = 0; i<n; ++i){
        scanf("%d", &up[mn[i] = i][0]); 
        if(--up[i][0] >= 0) g[up[i][0]].push_back(i);
        else rt = i;
    }
    up[rt][0] = rt;
    dfs(rt); efs(rt);
    for(int i = 0; i<n; ++i) T[SZ[E[i]] = i+1] = E[i];
    while(q--){
        int op, k, u; scanf("%d", &op);
        if(op == 1){
            scanf("%d", &k);
            printf("%d\n", T[sz = min(n, 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:18:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     int n, q, rt; scanf("%d %d", &n, &q); LOG = 32 - __builtin_clz(n);
      |                   ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%d", &up[mn[i] = i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:28:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         int op, k, u; scanf("%d", &op);
      |                       ~~~~~^~~~~~~~~~~
ballmachine.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |             scanf("%d", &k);
      |             ~~~~~^~~~~~~~~~
ballmachine.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |             scanf("%d", &u); --u;
      |             ~~~~~^~~~~~~~~~
ballmachine.cpp:25:17: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |     dfs(rt); efs(rt);
      |              ~~~^~~~

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