# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
83232 | teomrn | Ball Machine (BOI13_ballmachine) | C++14 | 1087 ms | 79512 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |