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 Y8o "Ball Machine"
#define maxn 100005
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
if(fopen(Y8o".inp", "r"))
{
freopen(Y8o".inp", "r", stdin);
freopen(Y8o".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
int n, Q, root, cnt;
int Min[maxn], cha[maxn][18], h[maxn], pos[maxn], a[maxn];
vector<int> o[maxn];
void dfs(int u)
{
for(int v : o[u])
{
h[v] = h[u] + 1, cha[v][0] = u;
for(int j = 1; j <= 17; j ++) cha[v][j] = cha[cha[v][j - 1]][j - 1];
dfs(v);
Min[u] = min({ Min[u], Min[v] });
}
Min[u] = min(Min[u], u);
}
void dfs2(int u)
{
for(int v : o[u]) dfs2(v);
a[++ cnt] = u;
pos[u] = cnt;
}
struct dl { int val, lazy; } st[4 * maxn];
void build(int id = 1, int l = 1, int r = n)
{
if(l == r)
{
st[id] = {0, -1};
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
st[id].val = st[id * 2].val + st[id * 2 + 1].val;
st[id].lazy = -1;
}
void down(int id, int l, int r)
{
int t = st[id].lazy;
if(t == -1) return ;
int mid = (l + r) >> 1;
st[id * 2] = {t * (mid - l + 1), t};
st[id * 2 + 1] = {t * (r - mid), t};
st[id].lazy = -1;
}
void update(int u, int v, int val, int id = 1, int l = 1, int r = n)
{
if(v < l || r < u) return ;
if(u <= l && r <= v)
{
st[id] = {val * (r - l + 1), val};
return ;
}
down(id, l, r);
int mid = (l + r) >> 1;
update(u, v, val, id * 2, l, mid);
update(u, v, val, id * 2 + 1, mid + 1, r);
st[id].val = st[id * 2].val + st[id * 2 + 1].val;
}
int get(int u, int v, int id = 1, int l = 1, int r = n)
{
if(v < l || r < u) return 0;
if(u <= l && r <= v) return st[id].val;
down(id, l, r);
int mid = (l + r) >> 1;
return get(u, v, id * 2, l, mid) + get(u, v, id * 2 + 1, mid + 1, r);
}
int add(int x)
{
int l = 1, r = n;
while(l <= r)
{
int mid = (l + r) >> 1;
if(get(1, mid) + x <= mid) r = mid - 1;
else l = mid + 1;
}
update(1, l, 1);
return a[l];
}
int jump(int u, int len)
{
for(int i = 0; i <= 17; i ++) if(gb(len, i)) u = cha[u][i];
return u;
}
int erase_(int u)
{
int l = 1, r = n;
while(l <= r)
{
int mid = (l + r) >> 1, v = jump(u, mid);
if(v != 0 && get(pos[v], pos[v]) == 1) l = mid + 1;
else r = mid - 1;
}
int par = jump(u, r);
update(pos[par], pos[par], 0);
return h[u] - h[par];
}
int dd[maxn];
void solve()
{
cin >> n >> Q;
for(int i = 1, v; i <= n; i ++)
{
cin >> v;
if(v == 0) root = i;
else o[v].push_back(i);
}
memset(Min, 0x3f, sizeof Min);
dfs(root);
for(int i = 1; i <= n; i ++) if(o[i].size())
sort(o[i].begin(), o[i].end(), [](int x, int y) { return Min[x] < Min[y]; });
dfs2(root);
build();
for(int i = 1, id, u; i <= Q; i ++)
{
cin >> id >> u;
if(id == 1) cout << add(u) << '\n';
else cout << erase_(u) << '\n';
// if(id == 1)
// {
// int pos = -1;
// for(int j = 1; j <= n, u; j ++)
// {
// if(dd[j]) continue;
// dd[j] = 1, pos = a[j], u --;
// }
// cout << pos << '\n';
// }
// else
// {
// int dem = 0;
// while(dd[ pos[cha[u][0]] ]) u = cha[u][0], dem ++;
// cout << dem << '\n', dd[pos[u]] = 0;
// }
}
}
int main()
{
iof();
int nTest = 1;
// cin >> nTest;
while(nTest --) {
solve();
}
ctime();
return 0;
}
Compilation message (stderr)
ballmachine.cpp: In function 'void iof()':
ballmachine.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | freopen(Y8o".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | freopen(Y8o".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |