#include <bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for (int i = x; i < y; i++)
const int mx = 1e5 + 5;
int n, q, to[mx], dep[mx], tin[mx], tout[mx], ti, cyc[mx]; bool vis[mx], active[mx];
vector<int> startDFS, adj[mx];
template<int sz> struct segTreeRP{
int seg[sz * 2];
int comb(int a, int b){
return tin[a] > tin[b] ? a : b; //we want lower node so greatest tin val
}
void upd(int l, int r, int v){
for (l += sz, r += sz; l <= r; r /= 2, l /= 2){
if (l % 2 == 1) seg[l] = comb(seg[l], v), l++;
if (r % 2 == 0) seg[r] = comb(seg[r], v), r--;
}
}
int qry(int i){
int ret = 0;
for (i += sz; i; i /= 2) ret = comb(ret, seg[i]);
return ret;
}
};segTreeRP<mx> st;
void findStartPts(int cur){
active[cur] = vis[cur] = 1; int nxt = to[cur];
if (!nxt) startDFS.push_back(cur); //endpoint of chain
else{
if (!vis[nxt]) findStartPts(nxt);
else if (active[nxt]) startDFS.push_back(cur); //part of cycle
}
active[cur] = 0;
}
bool isAnc(int A, int B){
return tin[A] <= tin[B] and tout[A] >= tout[B];
}
void dfs(int cur){
tin[cur] = ++ti;
for (int nxt : adj[cur]){
if (!tin[nxt]) dep[nxt] = dep[cur] + 1, dfs(nxt);
else cyc[nxt] = cur;
}
tout[cur] = ti;
}
void rem(int X){ //remove edge outgoing from X
if (cyc[X]) cyc[X] = 0;
else st.upd(tin[X], tout[X], X);
}
int solve(int A, int B){ //A goes to B
int ret = 0, root = st.qry(tin[A]);
if (A == B) return (isAnc(B, cyc[root]) ? 0 : -1);
if (A == B or !isAnc(B, A)){ //go to root and use cycle
ret += dep[A] - dep[root] + 1;
A = cyc[root];
}
if (isAnc(B, A) and tin[B] >= tin[root]) ret += dep[A] - dep[B];
else ret = -1;
return ret;
}
int main(){
cin >> n;
FOR(i, 1, n + 1){
cin >> to[i];
if (to[i]) adj[to[i]].push_back(i);
}
FOR(i, 1, n + 1) if (!vis[i]) findStartPts(i);
for (int i : startDFS){
dfs(i);
st.upd(tin[i], tout[i], i);
}
cin >> q;
while (q--){
int tp, A, B; cin >> tp;
if (tp == 1) cin >> A, rem(A);
else cin >> A >> B, cout<<solve(A, B)<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
