#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
template<int SZ> struct DSU {
int par[SZ], sz[SZ];
DSU() {
F0R(i,SZ) par[i] = i, sz[i] = 1;
}
int get(int x) { // path compression
if (par[x] != x) par[x] = get(par[x]);
return par[x];
}
bool unite(int x, int y) { // union-by-rank
x = get(x), y = get(y);
if (x == y) return 0;
if (sz[x] < sz[y]) swap(x,y);
sz[x] += sz[y], par[y] = x;
return 1;
}
};
DSU<MX> D;
int N, M, nex[MX][17], bad[MX], depth[MX];
pi cyc[MX]; // #, pos
int cycsz[MX];
set<int> lef[MX];
vector<array<int,3>> q;
vi ret;
void addEdge(int x) {
D.unite(x,nex[x][0]);
if (cyc[x].f) lef[cyc[x].f].erase(cyc[x].s);
}
bool con(int t, int y) {
assert(t != y);
int co = cyc[t].f;
t = cyc[t].s, y = cyc[y].s;
auto it = lef[co].lb(t);
if (t > y) {
if (it != lef[co].end()) return 0;
it = lef[co].begin();
}
return it == lef[co].end() || *it >= y;
}
int dis(int t, int y) {
int cur = cyc[y].s-cyc[t].s;
if (cur < 0) cur += cycsz[t];
return cur;
}
int anc(int x, int d) {
F0Rd(i,17) if (d&(1<<i)) x = nex[x][i];
return x;
}
int query(int x, int y) {
if (D.get(x) != D.get(y)) return -1;
if (depth[x] >= depth[y]) {
int t = anc(x,depth[x]-depth[y]);
if (t == y) return depth[x]-depth[y];
}
if (depth[y]) return -1;
int t = anc(x,depth[x]);
if (con(t,y)) return depth[x]+dis(t,y);
return -1;
}
int vis[MX];
void solve(int x) {
int X = x;
vi cur;
while (1) {
// cout << "AH " << x << " " << X << " " << vis[X] << "\n";
if (X == 0) return;
if (vis[X] == 0) {
vis[X] = x;
} else if (vis[X] == x) {
vis[X] += N;
cur.pb(X);
} else if (vis[X] == x+N) {
break;
} else return;
X = nex[X][0];
}
// cout << "OH " << x << " " << sz(cur) << " " << cur[0] << "\n";
F0R(i,sz(cur)) {
cyc[cur[i]] = {x,i};
cycsz[cur[i]] = sz(cur);
lef[x].insert(i);
}
}
int getDepth(int x) {
if (depth[x]) return depth[x];
if (x == 0 || vis[x] > N) return 0;
return depth[x] = getDepth(nex[x][0])+1;
}
void process() {
// cyc, cycsz, lef
FOR(i,1,N+1) solve(i);
FOR(i,1,N+1) if (vis[i] <= N) {
depth[i] = getDepth(i);
// cout << "BLAH " << i << " " << depth[i] << "\n";
}
/*FOR(i,1,N+1) {
cout << cyc[i].f << " " << cyc[i].s << " " << cycsz[i] << " " << depth[i] << "\n";
}*/
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
FOR(i,1,N+1) {
cin >> nex[i][0];
if (nex[i][0] == i) nex[i][0] = 0;
}
FOR(i,1,17) FOR(j,1,N+1) nex[j][i] = nex[nex[j][i-1]][i-1];
process();
cin >> M;
F0R(i,M) {
int t; cin >> t;
if (t == 1) {
int a; cin >> a; bad[a] = 1;
q.pb({1,a,0});
} else {
int a,b; cin >> a >> b;
q.pb({2,a,b});
}
}
FOR(i,1,N+1) if (!bad[i] && nex[i][0]) addEdge(i);
reverse(all(q));
for (auto a: q) {
if (a[0] == 1) addEdge(a[1]);
else ret.pb(query(a[1],a[2]));
}
reverse(all(ret));
for (int i: ret) cout << i << "\n";
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
6216 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6560 KB |
Output is correct |
| 3 |
Correct |
9 ms |
6560 KB |
Output is correct |
| 4 |
Correct |
12 ms |
6708 KB |
Output is correct |
| 5 |
Correct |
12 ms |
6716 KB |
Output is correct |
| 6 |
Correct |
15 ms |
7348 KB |
Output is correct |
| 7 |
Correct |
17 ms |
7608 KB |
Output is correct |
| 8 |
Correct |
16 ms |
8016 KB |
Output is correct |
| 9 |
Correct |
18 ms |
8204 KB |
Output is correct |
| 10 |
Correct |
21 ms |
8492 KB |
Output is correct |
| 11 |
Correct |
142 ms |
24704 KB |
Output is correct |
| 12 |
Correct |
119 ms |
24704 KB |
Output is correct |
| 13 |
Correct |
150 ms |
24704 KB |
Output is correct |
| 14 |
Correct |
107 ms |
24704 KB |
Output is correct |
| 15 |
Correct |
152 ms |
25076 KB |
Output is correct |
| 16 |
Correct |
107 ms |
26564 KB |
Output is correct |
| 17 |
Correct |
138 ms |
32396 KB |
Output is correct |
| 18 |
Correct |
159 ms |
34436 KB |
Output is correct |
| 19 |
Correct |
169 ms |
36408 KB |
Output is correct |
| 20 |
Correct |
138 ms |
41780 KB |
Output is correct |
