#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, dep[N], root[N], cycle[N], parent[N], tree[4 * N], p[N], pos[N],n, np, in[N], f[N], st[N], en[N];
int timer, tmin[N], tmout[N];
vector<int> V[N];
vector<int> x;
void dfs(int u,int p, int r) {
dep[u] = dep[p] + 1;
root[u] = r;
tmin[u] = ++ timer;
for(int i = 0; i < V[u].size(); i++) {
if(V[u][i] == p || cycle[V[u][i]]) continue;
dfs(V[u][i], u, r);
}
tmout[u] = timer;
}
int find(int u) {
return (parent[u] == u ? u : parent[u] = find(parent[u]));
}
void merge(int u,int v) {
u = find(u), v = find(v);
if(u == v) return;
parent[v] = u;
}
void upd(int u,int ind,int l,int r) {
if(l > ind ||r < ind) return;
if(l == r) {
tree[u] = 1;
return;
}
int mid = (l + r) / 2;
upd(2 * u, ind, l, mid); upd(2 * u + 1, ind, mid + 1, r);
tree[u] = min(tree[2 * u], tree[2 * u + 1]);
}
int get(int u,int st,int en,int l, int r) {
if(l > en || r < st) return 1;
if(st <= l && r <= en) return tree[u];
int mid = (l + r) / 2;
return get(2 * u, st, en, l, mid) & get(2 * u + 1, st, en, mid + 1, r);
}
bool check(int u,int v) {
return (tmin[u] <= tmin[v] && tmin[v] <= tmout[u]);
}
main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> p[i], in[p[i]]++, V[p[i]].push_back(i);
queue<int> q;
for(int i = 1; i <= n; i++) {
if(!in[i]) q.push(i);
}
while(q.size()) {
int u = q.front();
q.pop();
f[u] = 1;
in[p[u]]--;
if(p[u] && !in[p[u]]) q.push(p[u]);
}
int id = 0, idx = 0;
for(int i = 1; i <= n; i++) {
if(!f[i]) {
int u = i;
id++;
st[id] = idx + 1;
while(u && !f[u]) {
cycle[u] = id;
pos[u] = ++idx;
f[u] = 1;
en[id] = idx;
u = p[u];
}
}
if(cycle[i]) dfs(i, 0, i);
}
dfs(0, 0, 0);
int m;
memset(f, 0, sizeof(f));
cin >> m;
vector<int> ty(m + 5), v(m + 5), u(m + 5);
for(int i = 1; i <= m; i++) {
cin >> ty[i];
if(ty[i] == 1) cin >> v[i], f[v[i]] = 1;
else cin >> u[i] >> v[i];
}
for(int i = 1; i <= n; i++) parent[i] = i;
for(int i = 1; i <= n; i++) {
if(!f[i] && p[i]) merge(i, p[i]), upd(1, pos[i], 1, n);
}
for(int i = m; i >= 1; i--) {
if(ty[i] == 1) {
if(p[v[i]]) merge(v[i], p[v[i]]), upd(1, pos[v[i]], 1, n);
continue;
}
if(check(v[i], u[i]) && find(v[i]) == find(u[i])) x.push_back(dep[u[i]] - dep[v[i]]);
else
if(v[i] != root[v[i]]) x.push_back(-1);
else if(cycle[root[u[i]]] != cycle[root[v[i]]]) x.push_back(-1);
else if(find(u[i]) != find(root[u[i]]) || find(v[i]) != find(root[v[i]]))x.push_back(-1);
else {
int ans = dep[u[i]] + dep[v[i]] - 2;
u[i] = root[u[i]]; v[i] = root[v[i]];
int c = cycle[u[i]];
u[i] = pos[u[i]], v[i] = pos[v[i]];
if(u[i] <= v[i]) {
if(get(1, u[i], v[i] - 1, 1, n)) x.push_back(v[i] - u[i] + ans);//cout << v[i] - u[i] + ans << endl;
else x.push_back(-1);
}
else {
if(get(1, u[i], en[c], 1, n) && get(1, st[c], v[i] - 1, 1, n)) {
x.push_back( en[c] - u[i] + 1 + v[i] - st[c] + ans );
}
else x.push_back(-1);
}
}
}
for(int i = (int)x.size() - 1; i >= 0; i--) cout << x[i] <<"\n";
}
Compilation message
specialg.cpp: In function 'void dfs(long long int, long long int, long long int)':
specialg.cpp:16:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
specialg.cpp: At global scope:
specialg.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
49 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6860 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6928 KB |
Output is correct |
| 3 |
Correct |
6 ms |
6932 KB |
Output is correct |
| 4 |
Correct |
9 ms |
7244 KB |
Output is correct |
| 5 |
Correct |
6 ms |
6896 KB |
Output is correct |
| 6 |
Correct |
20 ms |
7832 KB |
Output is correct |
| 7 |
Correct |
20 ms |
7820 KB |
Output is correct |
| 8 |
Correct |
20 ms |
7880 KB |
Output is correct |
| 9 |
Correct |
22 ms |
7876 KB |
Output is correct |
| 10 |
Correct |
28 ms |
7816 KB |
Output is correct |
| 11 |
Correct |
184 ms |
24388 KB |
Output is correct |
| 12 |
Correct |
126 ms |
18480 KB |
Output is correct |
| 13 |
Correct |
163 ms |
21308 KB |
Output is correct |
| 14 |
Correct |
133 ms |
17756 KB |
Output is correct |
| 15 |
Correct |
125 ms |
18940 KB |
Output is correct |
| 16 |
Correct |
139 ms |
18764 KB |
Output is correct |
| 17 |
Correct |
163 ms |
23720 KB |
Output is correct |
| 18 |
Correct |
183 ms |
23684 KB |
Output is correct |
| 19 |
Correct |
156 ms |
23736 KB |
Output is correct |
| 20 |
Correct |
175 ms |
24380 KB |
Output is correct |
