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>
#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
using namespace std;
typedef long long LL;
typedef pair <int, int> II;
const int N = 1e5 + 10;
int n, q, Root, timer = 0, eulerSize = 0;
int x[N], V[N], c[N], pos[N], euler[N];
int headChain[N], szChain[N], p[N], f[N];
bool ban[N];
vector <int> adj[N];
set <II> S;
bool CMP(int x, int y) {
return f[x] < f[y];
}
void DFS(int u) {
f[u] = u;
REP(k, 0, adj[u].size()) {
int v = adj[u][k];
DFS(v);
f[u] = min(f[u], f[v]);
}
}
void EulerTour(int u) {
REP(k, 0, adj[u].size()) {
int v = adj[u][k];
EulerTour(v);
}
euler[++eulerSize] = u;
}
int Insert(int num) {
while (num > 0) {
int u = S.begin() -> second; S.erase(S.begin());
ban[u] = true;
--num;
if (num == 0) return u;
}
assert(false);
}
int Remove(int u) {
int ans = 0;
while (ban[p[u]] == true) {
++ans;
u = p[u];
}
ban[u] = false;
S.insert(II(pos[u], u));
return ans;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("ans.txt", "w", stdout);
#endif // LOCAL
scanf("%d%d", &n, &q);
FOR(i, 1, n) {
scanf("%d", &p[i]);
if (p[i] == 0) Root = i;
else adj[p[i]].push_back(i);
}
DFS(Root);
FOR(i, 1, n) sort(adj[i].begin(), adj[i].end(), CMP);
EulerTour(Root);
FOR(i, 1, eulerSize) pos[euler[i]] = i;
FOR(i, 1, n) S.insert(II(pos[i], i));
FOR(timer, 1, q) {
int t, u; scanf("%d%d", &t, &u);
if (t == 1) printf("%d\n", Insert(u));
else printf("%d\n", Remove(u));
}
return 0;
}
Compilation message (stderr)
ballmachine.cpp: In function 'void DFS(int)':
ballmachine.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
^
ballmachine.cpp:32:5: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^
ballmachine.cpp: In function 'void EulerTour(int)':
ballmachine.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
^
ballmachine.cpp:40:5: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:74:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &q);
^
ballmachine.cpp:76:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p[i]);
^
ballmachine.cpp:86:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int t, u; scanf("%d%d", &t, &u);
^
# | 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... |