This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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) {
int inv = 0;
if (h[a] < h[b])
swap(a, b), inv = 1;
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 inv ^ (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 && tata[where])
free_nodes.push(tata[where]);
}
int rem(int where)
{
assert(taken[where]);
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--) {
assert(!free_nodes.empty());
int q = free_nodes.top().nod;
free_nodes.pop();
while (nr_fii_activi[q] || taken[q]) {
assert(!free_nodes.empty());
q = free_nodes.top().nod;
free_nodes.pop();
}
last = q;
add(q);
}
cout << last << '\n';
}
else
cout << rem(x) << '\n';
}
return 0;
}
Compilation message (stderr)
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:115:33: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
cout << last << '\n';
^~~~
ballmachine.cpp:95:17: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
RMQ::dfs(root, 0);
~~~~~~~~^~~~~~~~~
# | 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... |