/* Includes */
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/* Using libraries */
using namespace std;
using namespace __gnu_pbds;
/* Some libraries utils */
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/* Defines */
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define ld long double
#define vc vector
#define pb push_back
#define out(a) for (int i: a) cout << i << ' ';
#define graph(n, g) for (int i = 0; i < n; ++i) {int u, v; cin >> u >> v; --u; --v; g[u].push_back(v); g[v].push_back(u);}
#define eb emplace_back
#define pii pair <int, int>
#define sz(a) (int) a.size()
#define forn(i, n) for(int i = 0; i < n; ++i)
/* Constants */
const int inf = 1e15 + 7, mod = 1e9 + 7, maxn = 305, maxc = 27;
/* Utils */
class Utils {
public:
class Modular {
private:
int n, md;
public:
Modular (): n(0), md(mod){}
Modular (int n): md(mod) {
this->n = normalize(n);
}
Modular (int n, int md): md(md) {
this->n = normalize(n);
}
int normalize (int x) {
if (abs(x) >= md) x %= md;
if (x < 0) return x + md;
return x;
}
Modular& operator = (int &x) {
this->n = normalize(x);
return *this;
}
Modular& operator += (const Modular &b) {return *this = *this + b;}
Modular& operator -= (const Modular &b) {return *this = *this - b;}
Modular& operator *= (const Modular &b) {return *this = *this * b;}
Modular& operator /= (const Modular &b) {return *this = *this / b;}
friend const Modular operator + (const Modular &a, const Modular &b) {
assert(a & b);
return Modular(a.n + b.n, a.md);
}
friend const Modular operator - (const Modular &a, const Modular &b) {
assert(a & b);
return Modular(a.n - b.n, a.md);
}
friend const Modular operator * (const Modular &a, const Modular &b) {
assert(a & b);
return Modular(a.n * b.n, a.md);
}
friend const Modular operator / (const Modular &a, const Modular &b) {
assert(a & b);
return Modular(a.n * Utils::Numbers::inverse(b.n, b.md), a.md);
}
friend ostream& operator << (ostream &os, const Modular& b) {
return os << b.n;
}
friend istream& operator >> (istream &os, Modular& b) {
os >> b.n;
b = Modular(b.n, b.md);
return os;
}
bool operator == (const Modular &b) const {
return n == b.n;
}
bool operator != (const Modular &b) const {
return !(*this == b);
}
friend bool operator & (const Modular &a, const Modular &b) {
return a.md == b.md;
}
};
class Numbers {
public:
using mint = Utils::Modular;
int static gcd (int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int static lcm (int a, int b) {
if (a == 0 && b == 0) return 0;
return a / Utils::Numbers::gcd(a, b) * b;
}
int static gcdex (int a, int b, int &x, int &y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
int x1, y1;
int d = gcdex(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return d;
}
int static inverse (int a, int m) {
int x, y;
int g = Utils::Numbers::gcdex(a, m, x, y);
assert(g == 1);
return (x % m + m) % m;
}
mint static bin_pow (mint a, int b, int m) {
mint res(1, m);
while (b) {
if (b & 1)
res *= a;
a *= a;
b >>= 1;
}
return res;
}
int static bin_pow (int a, int b, int m) {
int res = 1;
while (b) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
int static g (int n) {
return n ^ (n >> 1);
}
int static rev_g (int n) {
int f = 0;
for (; n; n >>= 1) f ^= n;
return f;
}
int static phi (int n) {
int f = n;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
while (n % i == 0) n /= i;
f -= f / i;
}
}
if (n > 1) f -= f / n;
return f;
}
};
class Combinatoric {
public:
using mint = Utils::Modular;
int maxn, mod;
vc <mint> fact, inv;
Combinatoric(int maxn, int mod = 1e9 + 7): maxn(maxn), mod(mod) {
fact.resize(maxn + 1, mint(0, mod));
inv.resize(maxn + 1, mint(0, mod));
fact[0] = fact[1] = mint(1, mod);
for (int i = 2; i <= maxn; ++i) {
fact[i] = fact[i - 1] * mint(i, mod);
}
inv[maxn] = mint(1, mod) / fact[maxn];
for (int i = maxn; i >= 1; --i) {
inv[i - 1] = inv[i] * mint(i, mod);
}
}
mint C (int n, int k) {
if (k > n) return 1;
return fact[n] * inv[n - k] * inv[k];
}
mint F (int n) {
return fact[n];
}
mint InvF (int n) {
return inv[n];
}
};
class bitset {
private:
using T = unsigned long long;
T SZ = 6;
T base = 1ll << SZ;
T mod = base - 1;
T n;
public:
vc <T> t;
bitset (T n) {
this->n = n;
t.resize((n + base - 1) / base);
}
T operator [](T i) {
return t[i >> SZ] & (1 << (i & mod));
}
void set (T i, T val) {
if ((*this)[i] == val) return;
t[i >> SZ] ^= 1 << (i & mod);
}
};
class Geometric {
public:
/* Point (and vector) */
class pt {
public:
ld x, y;
int i = -1;
pt (ld x = 0, ld y = 0, int i = -1): x(x), y(y), i(i){}
pt operator - () const {return pt(-x, -y);}
pt operator + (pt &b) const {return pt(x + b.x, y + b.y);}
pt operator - (pt &b) const {return pt(x - b.x, y - b.y);}
pt& operator = (pt &b) {this->x = b.x, this->y = b.y;}
ld operator * (pt &b) const {return x * b.x + y * b.y;}
ld operator ^ (pt &b) const {return x * b.y - b.x * y;}
bool operator == (pt &b) const {return x == b.x && y == b.y;}
bool operator != (pt &b) const {return !(*this == b);}
bool operator < (pt &b) const {return x == b.x ? y < b.y : x < b.x;}
bool operator <= (pt &b) const {return *this < b || *this == b;}
bool operator > (pt &b) const {return !(*this <= b);}
bool operator >= (pt &b) const {return *this > b || *this == b;}
friend ostream& operator << (ostream &os, pt &a) {return os << a.x << ' ' << a.y;}
friend istream& operator >> (istream &os, pt &a) {return os >> a.x >> a.y;}
ld operator [](int j) {return j == 0 ? x : y;}
ld angle () {
if (x == 0 && y == 0) return -1;
if (x == 0)
return y > 0 ? 90 : 270;
ld t = atan(y / x) * (360 );
if (x > 0)
return y >= 0 ? t : t + 360;
return t + 180;
}
ld len_sq () {return x * x + y * y;}
ld length () {return sqrtl(this->len_sq());}
};
using pt = Utils::Geometric::pt;
ld orientation (pt a, pt b, pt c) {
pt ab = b - a, ac = c - a;
ld sa = ab ^ ac;
if (sa > 0) return 1;
if (sa == 0) return 0;
if (sa < 0) return -1;
}
};
};
using mint = Utils::Modular;
using Math = Utils::Numbers;
int n, q, logn, root, ti, last;
vc <vc <int>> g, p;
vc <vc <pii>> to;
vc <int> used, tin, deg, cnt, h;
int precalc (int u, int t = -1) {
for (int i = 1; i < logn; ++i) {
p[u][i] = p[p[u][i - 1]][i - 1];
}
int ans = inf;
for (int v: g[u]) {
if (v != t) {
h[v] = h[u] + 1;
int tmp = precalc(v, u);
ans = min(ans, tmp);
to[u].pb({tmp, v});
}
}
sort(to[u].begin(), to[u].end());
ans = min(ans, u);
return ans;
}
void dfs (int u) {
tin[u] = ti++;
for (auto &[mysor, v]: to[u]) {
dfs(v);
}
}
bool cmp (int i, int j) {
return tin[i] < tin[j];
}
void solve () {
cin >> n >> q;
ti = 0;
logn = __lg(n) + 1;
g.resize(n); p.resize(n, vc <int> (logn)); to.resize(n); used.resize(n); tin.resize(n); deg.resize(n); cnt.resize(n); h.resize(n);
for (int i = 0; i < n; ++i) {
int u;
cin >> u;
if (u == 0) {
root = i;
continue;
}
--u;
g[u].pb(i);
g[i].pb(u);
deg[u]++;
p[i][0] = u;
}
forn (i, logn) p[root][i] = root;
precalc(root);
auto check = [&](int u) {
return !used[u];
};
dfs(root);
set <int, decltype(&cmp)> s(cmp);
forn (i, n) {
if (deg[i] == 0) {
s.insert(i);
}
}
while (q--) {
int cmd, x;
cin >> cmd >> x;
if (cmd == 1) {
while (x--) {
int u = *s.begin(); last = u;
int v = p[u][0];
used[u] = 1;
if (u != root) {
cnt[v]++;
if (cnt[v] == deg[v]) {
s.insert(v);
}
}
s.erase(u);
}
cout << last + 1 << '\n';
} else {
int c = 0; --x;
if (used[root]) {
used[root] = 0;
s.insert(root);
cout << h[x] << '\n';
continue;
}
for (int l = logn - 1; ~l; --l) {
if (!check(p[x][l])) {
c += (1ll << l);
x = p[x][l];
}
}
used[x] = 0;
if (x != root) {
--cnt[p[x][0]];
s.erase(p[x][0]);
}
s.insert(x);
cout << c << '\n';
}
}
}
/* Starting and precalcing */
signed main() {
/* freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); */
fast;
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
Compilation message
ballmachine.cpp: In member function 'Utils::Geometric::pt& Utils::Geometric::pt::operator=(Utils::Geometric::pt&)':
ballmachine.cpp:220:66: warning: no return statement in function returning non-void [-Wreturn-type]
220 | pt& operator = (pt &b) {this->x = b.x, this->y = b.y;}
| ^
| return *this;
ballmachine.cpp: In function 'void dfs(long long int)':
ballmachine.cpp:282:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
282 | for (auto &[mysor, v]: to[u]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
214 ms |
23908 KB |
Output is correct |
| 3 |
Correct |
104 ms |
23912 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
2 ms |
588 KB |
Output is correct |
| 7 |
Correct |
2 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
588 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1612 KB |
Output is correct |
| 10 |
Correct |
30 ms |
5892 KB |
Output is correct |
| 11 |
Correct |
199 ms |
24076 KB |
Output is correct |
| 12 |
Correct |
104 ms |
23932 KB |
Output is correct |
| 13 |
Correct |
163 ms |
23960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
8752 KB |
Output is correct |
| 2 |
Correct |
310 ms |
41048 KB |
Output is correct |
| 3 |
Correct |
128 ms |
35132 KB |
Output is correct |
| 4 |
Correct |
100 ms |
12392 KB |
Output is correct |
| 5 |
Correct |
98 ms |
12420 KB |
Output is correct |
| 6 |
Correct |
92 ms |
12536 KB |
Output is correct |
| 7 |
Correct |
105 ms |
10748 KB |
Output is correct |
| 8 |
Correct |
35 ms |
8840 KB |
Output is correct |
| 9 |
Correct |
226 ms |
40648 KB |
Output is correct |
| 10 |
Correct |
302 ms |
41128 KB |
Output is correct |
| 11 |
Correct |
244 ms |
41088 KB |
Output is correct |
| 12 |
Correct |
279 ms |
37188 KB |
Output is correct |
| 13 |
Correct |
147 ms |
40536 KB |
Output is correct |
| 14 |
Correct |
134 ms |
35128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
20456 KB |
Output is correct |
| 2 |
Correct |
329 ms |
38288 KB |
Output is correct |
| 3 |
Correct |
163 ms |
36548 KB |
Output is correct |
| 4 |
Correct |
194 ms |
32456 KB |
Output is correct |
| 5 |
Correct |
243 ms |
32920 KB |
Output is correct |
| 6 |
Correct |
204 ms |
32896 KB |
Output is correct |
| 7 |
Correct |
213 ms |
30352 KB |
Output is correct |
| 8 |
Correct |
183 ms |
36548 KB |
Output is correct |
| 9 |
Correct |
286 ms |
40700 KB |
Output is correct |
| 10 |
Correct |
352 ms |
41348 KB |
Output is correct |
| 11 |
Correct |
353 ms |
41284 KB |
Output is correct |
| 12 |
Correct |
347 ms |
38248 KB |
Output is correct |
| 13 |
Correct |
300 ms |
46004 KB |
Output is correct |
| 14 |
Correct |
259 ms |
35632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
341 ms |
40916 KB |
Output is correct |
| 2 |
Correct |
324 ms |
38180 KB |
Output is correct |
| 3 |
Correct |
159 ms |
45680 KB |
Output is correct |
| 4 |
Correct |
369 ms |
40964 KB |
Output is correct |
| 5 |
Correct |
383 ms |
41380 KB |
Output is correct |
| 6 |
Correct |
306 ms |
41304 KB |
Output is correct |
| 7 |
Correct |
365 ms |
38192 KB |
Output is correct |
| 8 |
Correct |
211 ms |
45712 KB |
Output is correct |
| 9 |
Correct |
192 ms |
35356 KB |
Output is correct |
