#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 1e5 + 10, MOD = 1e9 + 7;
int H[N], St[N], R[N], M[N], M2[N], Ft[N], t[N], A[N], B[N], rt[N], nxt[N], n, q, tim;
vector<int> adj[N]; pii E[N];
int preFind(int v) {
return !rt[v] ? v : rt[v] = preFind(rt[v]);
}
int Find(int v) {
if (!rt[v]) return v;
int p = rt[v]; rt[v] = Find(rt[v]), H[v] += H[p];
return rt[v];
}
void preDFS(int v) {
St[v] = tim++; M2[v] = 1;
for (int &u : adj[v])
preDFS(u);
Ft[v] = tim;
}
int D(int u, int v) {
assert(Find(u) == Find(v));
if (!(St[v] <= St[u] && Ft[u] <= Ft[v])) return MOD;
return H[u] - H[v];
}
int query(int u, int v) {
if (Find(u) != Find(v)) return -1;
int ret = D(u, v);
if (E[Find(u)].F)
ret = min(ret, D(u, E[Find(u)].F) + D(E[Find(u)].S, v) + 1);
return ret >= MOD ? -1 : ret;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &nxt[i]);
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
scanf("%d", &t[i]);
if (t[i] > 1) scanf("%d%d", &A[i], &B[i]);
else scanf("%d", &A[i]), M[A[i]] = 1;
}
for (int i = 1; i <= n; i++) {
if (!M[i] && nxt[i]) {
int u = preFind(i), v = preFind(nxt[i]);
if (u != v) {
adj[nxt[i]].push_back(u), assert(u == i), rt[u] = v;
}
}
}
for (int i = q; i; i--) {
if (t[i] > 1) continue;
int v = A[i], u = preFind(nxt[A[i]]); assert(nxt[A[i]]);
if (u == v) continue;
adj[nxt[v]].push_back(v), rt[v] = u;
}
for (int i = 1; i <= n; i++)
if (!M2[i] && preFind(i) == i) preDFS(i);
memset(rt, 0, sizeof rt);
for (int i = 1; i <= n; i++) {
if (!M[i] && nxt[i]) {
int u = Find(i), v = Find(nxt[i]); assert(u == i);
if (u == v) E[i] = {i, nxt[i]};
else {
H[i] = H[nxt[i]] + 1;
rt[i] = v;
}
}
}
for (int i = q; i; i--) {
if (t[i] < 2) {
int u = Find(A[i]), v = Find(nxt[A[i]]); assert(u == A[i]), assert(nxt[A[i]]);
if (u == v) E[A[i]] = {A[i], nxt[A[i]]};
else H[A[i]] = H[nxt[A[i]]] + 1, rt[A[i]] = v;
} else {
R[i] = query(A[i], B[i]);
}
}
for (int i = 1; i <= q; i++)
if (t[i] > 1) printf("%d\n", R[i]);
return 0;
}
Compilation message
specialg.cpp: In function 'int main()':
specialg.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
specialg.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d", &nxt[i]);
| ~~~~~^~~~~~~~~~~~~~~
specialg.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
specialg.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d", &t[i]);
| ~~~~~^~~~~~~~~~~~~
specialg.cpp:55:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | if (t[i] > 1) scanf("%d%d", &A[i], &B[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
specialg.cpp:56:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | else scanf("%d", &A[i]), M[A[i]] = 1;
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3148 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3148 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3276 KB |
Output is correct |
| 5 |
Correct |
4 ms |
3148 KB |
Output is correct |
| 6 |
Correct |
11 ms |
3496 KB |
Output is correct |
| 7 |
Correct |
11 ms |
3540 KB |
Output is correct |
| 8 |
Correct |
11 ms |
3456 KB |
Output is correct |
| 9 |
Correct |
14 ms |
3532 KB |
Output is correct |
| 10 |
Correct |
11 ms |
3532 KB |
Output is correct |
| 11 |
Correct |
74 ms |
14436 KB |
Output is correct |
| 12 |
Correct |
63 ms |
10596 KB |
Output is correct |
| 13 |
Correct |
68 ms |
11772 KB |
Output is correct |
| 14 |
Correct |
80 ms |
9932 KB |
Output is correct |
| 15 |
Correct |
63 ms |
10376 KB |
Output is correct |
| 16 |
Correct |
64 ms |
10292 KB |
Output is correct |
| 17 |
Correct |
75 ms |
12996 KB |
Output is correct |
| 18 |
Correct |
75 ms |
13436 KB |
Output is correct |
| 19 |
Correct |
76 ms |
13188 KB |
Output is correct |
| 20 |
Correct |
72 ms |
15372 KB |
Output is correct |
