제출 #83232

#제출 시각아이디문제언어결과실행 시간메모리
83232teomrnBall Machine (BOI13_ballmachine)C++14
20.40 / 100
1087 ms79512 KiB
#include <bits/stdc++.h> using namespace std; const int NMAX = 100010; const int LGMAX = 18; vector <int> adia[NMAX + 10]; int nr_fii_activi[NMAX + 10]; bool taken[NMAX + 10]; int tata[NMAX + 10]; namespace RMQ { int h[NMAX + 10]; int stramos[LGMAX + 1][NMAX + 10]; int vmin[NMAX + 10]; void dfs(int nod, int tata) { h[nod] = 1 + h[tata]; vmin[nod] = nod; stramos[0][nod] = tata; for (int i = 1; i <= LGMAX; i++) stramos[i][nod] = stramos[i - 1][stramos[i - 1][nod]]; for (auto i : adia[nod]) { dfs(i, nod); vmin[nod] = min(vmin[nod], vmin[i]); } } bool mai_mic(int a, int b) { if (h[a] < h[b]) swap(a, b); for (int i = LGMAX; i >= 0; i--) if (h[a] - (1 << i) >= h[b]) a = stramos[i][a]; for (int i = LGMAX; i >= 0; i--) if (stramos[i][a] != stramos[i][b]) a = stramos[i][a], b = stramos[i][b]; return vmin[a] < vmin[b]; } } struct Node { Node(int x) : nod(x) { } int nod; bool operator< (const Node & n) const { return RMQ::mai_mic(n.nod, nod); } }; priority_queue <Node> free_nodes; void add(int where) { taken[where] = 1; nr_fii_activi[tata[where]]--; if (nr_fii_activi[tata[where]] == 0) free_nodes.push(tata[where]); } int rem(int where) { if (!taken[tata[where]]) { taken[where] = 0; nr_fii_activi[tata[where]]++; free_nodes.push(where); return 0; } int ans = 0; for (int i = LGMAX; i >= 0; i--) if (taken[RMQ::stramos[i][where]]) ans += (1 << i), where = RMQ::stramos[i][where]; taken[where] = 0; nr_fii_activi[tata[where]]++; free_nodes.push(where); return ans; } int main() { int n, m; ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; int root; for (int i = 1; i <= n; i++) { cin >> tata[i]; if (tata[i] == 0) root = i; adia[tata[i]].push_back(i); nr_fii_activi[tata[i]]++; } for (int i = 1; i <= n; i++) if (nr_fii_activi[i] == 0) free_nodes.push(i); RMQ::dfs(root, 0); while (m--) { int type, x; cin >> type >> x; if (type == 1) { int last; while (x--) { int q = free_nodes.top().nod; free_nodes.pop(); while (nr_fii_activi[q]) { q = free_nodes.top().nod; free_nodes.pop(); } last = q; add(q); } cout << last << '\n'; } else cout << rem(x) << '\n'; } return 0; }

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

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:117:29: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout << last << '\n';
                             ^~~~
ballmachine.cpp:99:13: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     RMQ::dfs(root, 0);
     ~~~~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...