#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), rt[u] = v; //assert(u == i);
}
}
}
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
school.cpp: In function 'int main()':
school.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
school.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]);
| ~~~~~^~~~~~~~~~~~~~~
school.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
school.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]);
| ~~~~~^~~~~~~~~~~~~
school.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]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
school.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 |
Incorrect |
2 ms |
3020 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
3020 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
3020 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
3020 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
3020 KB |
Output isn't correct |
| 6 |
Incorrect |
4 ms |
3020 KB |
Output isn't correct |
| 7 |
Incorrect |
6 ms |
3148 KB |
Output isn't correct |
| 8 |
Incorrect |
7 ms |
3276 KB |
Output isn't correct |
| 9 |
Incorrect |
7 ms |
3148 KB |
Output isn't correct |
| 10 |
Incorrect |
7 ms |
3276 KB |
Output isn't correct |
| 11 |
Incorrect |
9 ms |
3276 KB |
Output isn't correct |
| 12 |
Incorrect |
6 ms |
3220 KB |
Output isn't correct |
| 13 |
Incorrect |
21 ms |
4700 KB |
Output isn't correct |
| 14 |
Incorrect |
36 ms |
6004 KB |
Output isn't correct |
| 15 |
Runtime error |
185 ms |
262148 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
180 ms |
262148 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
175 ms |
262148 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
180 ms |
262148 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
193 ms |
262148 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
192 ms |
262148 KB |
Execution killed with signal 9 |
