#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
constexpr int n0 = 2e5 + 123, k0 = 18, inf = 1e9;
int n, m, a[n0], t[n0], used[n0], par[n0], up[k0][n0], mn[k0][n0];
int in[n0], out[n0], T, h[n0], lg[n0], head[n0], timer;
array <int, 3> q[n0];
vector <int> g[n0];
int arr[n0], k, sp[k0][n0], c[n0], cnt, sz[n0], pos[n0];
vector <int> vec;
void dfs(int v) {
used[v] = 1;
for (int to : g[v]) {
if (used[to] == 1) {
int u = v;
vec.clear();
while (u != to) vec.pb(u), u = par[u];
vec.pb(to);
cnt++;
for (int i : vec) {
c[i] = cnt, sz[cnt]++;
arr[++k] = t[i];
pos[i] = k;
}
for (int i : vec) arr[++k] = t[i];
} else {
par[to] = v;
if (used[to] == 0)
dfs(to);
}
}
used[v] = 2;
}
void go(int v, int p) {
if (c[v]) return;
if (p == v) head[v] = v;
used[v] = 1;
up[0][v] = p;
mn[0][v] = t[v];
for (int i = 1; i < k0; i++) {
up[i][v] = up[i - 1][up[i - 1][v]];
mn[i][v] = min(mn[i - 1][v], mn[i - 1][up[i - 1][v]]);
}
in[v] = ++T;
for (int to : g[v]) {
if (c[to] || to == p) continue;
h[to] = h[v] + 1;
head[to] = head[v];
go(to, v);
}
out[v] = T;
}
bool upper(int v, int u) {
return in[v] <= in[u] && out[u] <= out[v];
}
int getmin(int v, int u) {
if (v == u) return inf;
assert(upper(u, v));
int res = inf;
for (int i = k0 - 1; i >= 0; i--) {
if (!upper(up[i][v], u)) {
res = min(res, mn[i][v]);
v = up[i][v];
}
}
return min(res, mn[0][v]);
}
int get(int l, int r) {
int len = lg[r - l + 1];
return min(sp[len][l], sp[len][r - (1 << len) + 1]);
}
int cycle_dist(int v, int u) {
assert(c[v] && c[u]);
if (v == u) return 0;
if (c[v] != c[u]) return -1;
if (pos[v] < pos[u]) {
if (get(pos[v], pos[u] - 1) < timer) return -1;
return pos[u] - pos[v];
}
if (pos[v] < pos[u] + sz[c[u]]) {
if (get(pos[v], pos[u] + sz[c[u]] - 1) < timer) return -1;
return pos[u] + sz[c[u]] - pos[v];
}
assert(false);
}
int dist(int v, int u) {
if (c[v] && c[u]) return cycle_dist(v, u);
if (!c[v] && c[u]) {
int res = h[v] - h[head[v]] + 1;
if (getmin(v, head[v]) < timer) return -1;
if (t[head[v]] < timer) return -1;
v = par[head[v]];
if (!c[v]) return -1;
int d = cycle_dist(v, u);
if (d == -1) return -1;
return res + d;
}
if (!c[v] && !c[u]) {
if (!upper(u, v)) return -1;
if (getmin(v, u) < timer) return -1;
return h[v] - h[u];
}
return -1;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> q[i][0] >> q[i][1];
if (q[i][0] == 2) cin >> q[i][2];
else t[q[i][1]] = i;
}
for (int i = 1; i <= n; i++) {
if (t[i] == 0) t[i] = inf;
g[a[i]].pb(i);
}
for (int i = 1; i <= n; i++)
if (!used[i]) dfs(i);
for (int i = 1; i <= k; i++)
sp[0][i] = arr[i];
for (int i = 1; i < k0; i++)
for (int j = 1; j + (1 << i) - 1 <= k; j++)
sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
for (int i = 2; i <= k; i++)
lg[i] = lg[i / 2] + 1;
memset(& used, 0, sizeof(used));
for (int i = 1; i <= n; i++)
if (!used[i])
go(i, i);
for (int i = 1; i <= m; i++) {
if (q[i][0] == 2) {
timer = i;
cout << dist(q[i][1], q[i][2]) << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6400 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6528 KB |
Output is correct |
| 3 |
Correct |
6 ms |
6528 KB |
Output is correct |
| 4 |
Correct |
9 ms |
6528 KB |
Output is correct |
| 5 |
Correct |
8 ms |
6528 KB |
Output is correct |
| 6 |
Correct |
11 ms |
6912 KB |
Output is correct |
| 7 |
Correct |
11 ms |
7040 KB |
Output is correct |
| 8 |
Correct |
11 ms |
7044 KB |
Output is correct |
| 9 |
Correct |
11 ms |
7040 KB |
Output is correct |
| 10 |
Correct |
11 ms |
7040 KB |
Output is correct |
| 11 |
Correct |
82 ms |
39152 KB |
Output is correct |
| 12 |
Correct |
77 ms |
24568 KB |
Output is correct |
| 13 |
Correct |
91 ms |
30032 KB |
Output is correct |
| 14 |
Correct |
71 ms |
22392 KB |
Output is correct |
| 15 |
Correct |
78 ms |
25464 KB |
Output is correct |
| 16 |
Correct |
80 ms |
24956 KB |
Output is correct |
| 17 |
Correct |
93 ms |
35956 KB |
Output is correct |
| 18 |
Correct |
93 ms |
35956 KB |
Output is correct |
| 19 |
Correct |
95 ms |
35956 KB |
Output is correct |
| 20 |
Correct |
82 ms |
39152 KB |
Output is correct |
