#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct {
int type, x, y;
} qu[N];
int n, m, p[N], deg[N], h[N], to[N], root[N], pos[N], root_cir[N], sz[N], check[N], ans[N];
int par[N][20];
vector<int> a[N];
void dfs(int u, int p) {
par[u][0] = p;
for(int v: a[u]) if(v != p) {
if(deg[v]) continue;
h[v] = h[u] + 1;
root[v] = root[u];
dfs(v, u);
}
}
int cnt;
int lca(int u, int v) {
for(int i = 17; i >= 0; --i) if(h[par[u][i]] >= h[v]) u = par[u][i];
for(int i = 17; i >= 0; --i) if(h[par[v][i]] >= h[u]) v = par[v][i];
for(int i = 17; i >= 0; --i) if(par[v][i] != par[u][i])
u = par[u][i], v = par[v][i];
if(u != v) u = par[u][0];
return u;
}
void find_cir(int u, int root) {
int v = p[u];
check[u] = true;
pos[u] = sz[cnt]++;
root_cir[u] = cnt;
if(v == root) return;
find_cir(v, root);
}
int find(int u) {
if(to[u] == u) return u;
return to[u] = find(to[u]);
}
void join(int u, int v) {
u = find(u);
v = find(v);
if(u != v) to[u] = v;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> p[i];
a[p[i]].push_back(i);
deg[p[i]]++;
}
queue<int> Q;
for(int i = 1; i <= n; ++i) if(!deg[i]) Q.push(i);
while(Q.size()) {
int u = Q.front(); Q.pop();
if(p[u] == 0) continue;
deg[p[u]]--; if(!deg[p[u]]) Q.push(p[u]);
}
for(int i = 1; i <= n; ++i) if(deg[i] || p[i] == 0) {
root[i] = i;
dfs(i, i);
}
for(int i = 1; i <= n; ++i) if(deg[i] && !check[i]) {
cnt++;
find_cir(i, i);
}
for(int i = 1; i <= 17; ++i) for(int j = 1; j <= n; ++j)
par[j][i] = par[par[j][i - 1]][i - 1];
cin >> m;
for(int i = 1; i <= m; ++i) {
cin >> qu[i].type;
if(qu[i].type == 1) {
cin >> qu[i].x; qu[i].y = p[qu[i].x];
p[qu[i].x] = 0;
}
else cin >> qu[i].x >> qu[i].y;
}
for(int i = 1; i <= n; ++i) to[i] = i;
for(int i = 1; i <= n; ++i) if(p[i]) join(i, p[i]);
for(int i = m; i >= 1; --i) {
if(qu[i].type == 1) {
join(qu[i].x, qu[i].y);
}
else {
int s = qu[i].x, t = qu[i].y;
if(find(s) != find(t)) ans[i] = -1;
else {
if(root[s] == root[t]) {
int L = lca(s, t);
if(s != L && t != L) ans[i] = -1;
else ans[i] = abs(h[s] - h[t]);
}
else {
if(root[s] != s && root[t] != t)
ans[i] = -1;
else {
ans[i] += h[s] + h[t];
s = root[s]; t = root[t];
if(s <= t) ans[i] += pos[t] - pos[s];
else ans[i] += sz[root_cir[s]] - pos[s] + pos[t];
}
}
}
}
}
for(int i = 1; i <= m; ++i) if(qu[i].type == 2)
cout << ans[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
