# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
440697 | parsabahrami | Schools (IZhO13_school) | C++17 | 200 ms | 262148 KiB |
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>
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |