제출 #493174

#제출 시각아이디문제언어결과실행 시간메모리
493174RainbowbunnyBall Machine (BOI13_ballmachine)C++17
100 / 100
164 ms25440 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXL = 20; int n, q, Time, r; int mn[MAXN], e[MAXN], tout[MAXN], up[MAXN][MAXL], H[MAXN]; bool In[MAXN]; priority_queue <int, vector <int>, greater <int> > pq; vector <int> Adj[MAXN]; void DFS1(int node) { mn[node] = node; for(auto x : Adj[node]) { DFS1(x); mn[node] = min(mn[node], mn[x]); } } void DFS2(int node, int p) { sort(Adj[node].begin(), Adj[node].end(), [](int x, int y) { return mn[x] < mn[y]; }); up[node][0] = p; for(int i = 1; i < MAXL; i++) { up[node][i] = up[up[node][i - 1]][i - 1]; } for(auto x : Adj[node]) { H[x] = H[node] + 1; DFS2(x, node); } Time++; e[Time] = node; tout[node] = Time; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> q; for(int i = 1; i <= n; i++) { int id; cin >> id; if(id) { Adj[id].push_back(i); } else { r = i; } } DFS1(r); DFS2(r, r); for(int i = 1; i <= Time; i++) { pq.emplace(i); } while(q--) { int Type; cin >> Type; if(Type == 1) { int k, lst; cin >> k; for(int i = 1; i <= k; i++) { In[e[pq.top()]] = true; lst = e[pq.top()]; pq.pop(); } cout << lst << '\n'; } else { int k; cin >> k; int ii = k; for(int i = MAXL - 1; i >= 0; i--) { if(In[up[ii][i]]) { ii = up[ii][i]; } } cout << H[k] - H[ii] << '\n'; In[ii] = false; pq.push(tout[ii]); } } }

컴파일 시 표준 에러 (stderr) 메시지

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:83:28: warning: 'lst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |             cout << lst << '\n';
      |                            ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...