#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], bit[N];
int get(int t, int pos) {
//cout << t << ' ' << bit[t].size() << endl;
int res = 0;
for(pos; pos > 0; pos -= pos & -pos)
res += bit[t][pos];
return res;
}
void upd(int t, int pos) {
for(pos; pos <= sz[t]; pos += pos & -pos)
bit[t][pos]++;
}
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);
//cout << root_cir[6] << endl;
bit[cnt].assign(sz[cnt] + 5, 0);
}
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]);
if(i == root[i]) upd(root_cir[i], pos[i]);
}
for(int i = m; i >= 1; --i) {
if(qu[i].type == 1) {
join(qu[i].x, qu[i].y);
if(qu[i].x == root[qu[i].x]) {
upd(root_cir[qu[i].x], pos[qu[i].x]);
}
}
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];
int cir = root_cir[s];
if(s <= t) {
if(get(cir, pos[t] - 1) - get(cir, pos[s] - 1) != pos[t] - pos[s])
ans[i] = -1;
else ans[i] += pos[t] - pos[s];
}
else {
if(get(cir, sz[root_cir[s]]) - get(cir, pos[s] - 1) + get(cir, pos[t] - 1) != (sz[root_cir[s]]) - pos[s] + pos[t])
ans[i] = -1;
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';
}
Compilation message
specialg.cpp: In function 'int get(int, int)':
specialg.cpp:17:9: warning: statement has no effect [-Wunused-value]
for(pos; pos > 0; pos -= pos & -pos)
^
specialg.cpp: In function 'void upd(int, int)':
specialg.cpp:23:9: warning: statement has no effect [-Wunused-value]
for(pos; pos <= sz[t]; pos += pos & -pos)
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
5368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
