제출 #1094984

#제출 시각아이디문제언어결과실행 시간메모리
1094984SunbaeBall Machine (BOI13_ballmachine)C++17
24.80 / 100
94 ms21076 KiB
#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; } } }

컴파일 시 표준 에러 (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);
      |              ~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...