제출 #250809

#제출 시각아이디문제언어결과실행 시간메모리
250809Tc14Ball Machine (BOI13_ballmachine)C++17
71.67 / 100
1098 ms34168 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ve vector typedef long long ll; typedef pair<int, int> pii; const int INF = 1e9 + 10; const int MAXN = 100000; const int L = 20; int Root, HMax; int M[MAXN], C[MAXN], H[MAXN], P[MAXN], A[MAXN][L]; bool U[MAXN]; ve<int> G[MAXN]; priority_queue<int, ve<int>, greater<int>> PQ[MAXN]; bool sortFunction(int a, int b) { return M[a] < M[b]; } void dfs(int u) { int a, w; a = A[u][0]; for (int i = 0; i < L; i++) { A[u][i] = a; if (a != -1) a = A[a][i]; } M[u] = u; for (int v : G[u]) { dfs(v); M[u] = min(M[u], M[v]); } if (G[u].size() > 0) { sort(G[u].begin(), G[u].end(), sortFunction); for (int i = 0; i < G[u].size(); i++) { PQ[u].push(i); P[G[u][i]] = i; } w = G[u][0]; if (H[w] == HMax) { C[u] = A[C[w]][0]; H[u] = HMax; } else { C[u] = C[w]; H[u] = H[w] + 1; } } else { C[u] = u; H[u] = 0; } } int ins(int k) { int c, cNew, a, h, v; for (int i = 0; i < k; i++) { c = Root; while (c != C[c]) c = C[c]; U[c] = true; a = A[c][0]; if (a != -1) { PQ[a].pop(); if (PQ[a].size() > 0) { v = G[a][PQ[a].top()]; if (H[v] == HMax) { cNew = A[C[v]][0]; h = HMax; } else { cNew = C[v]; h = H[v] + 1; } } else { cNew = a; h = 0; } for (int j = 0; j < HMax; j++) { if (a != -1) { C[a] = cNew; H[a] = h; a = A[a][0]; if (h == HMax) cNew = A[cNew][0]; else h++; } else break; } } } return c; } int del(int u) { int a, v, r; r = 0; for (int i = L - 1; i >= 0; i--) { if (A[u][i] != -1 && U[A[u][i]]) { r += 1 << i; u = A[u][i]; } } U[u] = false; a = A[u][0]; if (a != -1) { PQ[a].push(P[u]); for (int j = 0; j < HMax; j++) { if (a != -1) { v = G[a][PQ[a].top()]; if (C[v] == u) { C[a] = u; H[a] = j + 1; } else break; a = A[a][0]; } else break; } } return r; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q, p, o, k, ans; cin >> n >> q; HMax = sqrt(n); for (int i = 0; i < n; i++) { cin >> p; p--; if (p != -1) G[p].push_back(i); else Root = i; A[i][0] = p; } dfs(Root); for (int i = 0; i < q; i++) { cin >> o >> k; if (o == 1) ans = ins(k) + 1; else ans = del(k - 1); cout << ans << "\n"; } return 0; }

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

ballmachine.cpp: In function 'void dfs(int)':
ballmachine.cpp:37:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < G[u].size(); i++) {
                         ~~^~~~~~~~~~~~~
ballmachine.cpp: In function 'int ins(int)':
ballmachine.cpp:99:12: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return c;
            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...