| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 88560 | wolfris | Ball Machine (BOI13_ballmachine) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, q, root, p[20][100015], h[100015];
vector <int> a[100015];
int c[100015], id[100015], node[100015], maxId;
priority_queue <int, vector <int>, greater <int>> heap;
bool ball[100015];
void dfs(int u) {
c[u] = u;
for (int v: a[u])
h[v] = h[u] + 1,
dfs(v), c[u] = min(c[u], c[v]);
}
bool cmp(int u, int v) {
return c[u] < c[v];
}
void assignId(int u) {
sort(a[u].begin(), a[u].end());
for (int v: a[u]) assignId(v);
id[u] = ++maxId; node[maxId] = u;
heap.push(maxId);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
for (int u = 1; u <= n; ++u) {
cin >> p[0][u];
if (p[0][u])
a[p[0][u]].push_back(u);
else root = u;
}
h[root] = 1; dfs(root); assignId(root);
for (int i = 1; (1 << i) <= n; ++i)
for (int u = 1; u <= n; ++u)
p[i][u] = p[i - 1][p[i - 1][u]];
for (int cmd, k; q--;) {
cin >> cmd >> k;
if (cmd == 1) {
int u;
while (k--)
u = node[heap.top()],
ball[u] = true, heap.pop();
cout << u << '\n';
}
else {
int u = k;
for (int i = log2(h[u]); i >= 0; --i)
if (ball[p[i][u]]) u = p[i][u];
ball[u] = false; heap.push(id[u]);
cout << h[k] - h[u] << '\n';
}
}
}