#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int,int> pi;
struct disj{
int pa[100005];
void init(int n){
for(int i=0; i<=n; i++) pa[i] = i;
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
bool uni(int p, int q){
p = find(p), q = find(q);
if(p == q) return 0;
pa[q] = p; return 1;
}
}disj;
struct query{
int t, a, b;
}q[100005];
int n, m, a[100005], kill[100005];
vector<int> graph[100005], rev[100005];
int indeg[100005];
int cyclab[100005], cycidx[100005], cycsz[100005], cycp;
int treein[100005], treeout[100005], root[100005], dep[100005], treep;
void dfs(int x, int r){
treein[x] = ++treep;
root[x] = r;
for(auto &i : rev[x]){
if(cyclab[i]) continue;
dep[i] = dep[x] + 1;
dfs(i, r);
}
treeout[x] = ++treep;
}
void proc_tree(){
for(int i=1; i<=n; i++){
if(a[i] == 0 || cyclab[i]){
dfs(i, i);
}
}
}
queue<int> que;
void proc_cycle(){
for(int i=1; i<=n; i++){
if(indeg[i] == 0) que.push(i);
}
while(!que.empty()){
int x = que.front();
que.pop();
if(!a[x]) continue;
indeg[a[x]]--;
if(indeg[a[x]] == 0) que.push(a[x]);
}
for(int i=1; i<=n; i++){
if(indeg[i] && !cyclab[i]){
int p = i;
cycp++;
while(!cyclab[p]){
cyclab[p] = cycp;
cycidx[p] = ++cycsz[cycp];
p = a[p];
}
}
}
}
inline bool inside(int a, int b){
return treein[a] <= treein[b] && treeout[b] <= treeout[a];
}
int solve(int p, int q){
if(cyclab[p] && cyclab[q]){
int dx = cycidx[q] - cycidx[p] + cycsz[cyclab[p]];
dx %= cycsz[cyclab[p]];
return dx;
}
if(cyclab[p] && !cyclab[q]){
return -1;
}
if(!cyclab[p] && cyclab[q]){
return dep[p] + solve(root[p], q);
}
if(inside(q, p)){
return dep[p] - dep[q];
}
return -1;
}
int main(){
cin >> n;
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
kill[i] = (a[i] == 0);
if(a[i]){
rev[a[i]].push_back(i);
graph[i].push_back(a[i]);
indeg[a[i]]++;
}
}
cin >> m;
for(int i=0; i<m; i++){
scanf("%d",&q[i].t);
if(q[i].t == 1){
scanf("%d",&q[i].a);
kill[q[i].a] = 1;
}
else{
scanf("%d %d",&q[i].a, &q[i].b);
}
}
reverse(q, q+m);
proc_cycle();
proc_tree();
disj.init(n);
for(int i=1; i<=n; i++){
if(!kill[i]) disj.uni(i, a[i]);
}
vector<int> stk;
for(int i=0; i<m; i++){
if(q[i].t == 1){
disj.uni(q[i].a, a[q[i].a]);
}
else{
if(disj.find(q[i].a) != disj.find(q[i].b)) stk.push_back(-1);
else stk.push_back(solve(q[i].a, q[i].b));
}
}
while(!stk.empty()){
printf("%d\n",stk.back());
stk.pop_back();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
11888 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
12024 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
11888 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
12072 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
11888 KB |
Output isn't correct |
| 6 |
Incorrect |
14 ms |
12152 KB |
Output isn't correct |
| 7 |
Incorrect |
9 ms |
12160 KB |
Output isn't correct |
| 8 |
Incorrect |
11 ms |
12172 KB |
Output isn't correct |
| 9 |
Incorrect |
9 ms |
12160 KB |
Output isn't correct |
| 10 |
Incorrect |
14 ms |
12176 KB |
Output isn't correct |
| 11 |
Incorrect |
80 ms |
18912 KB |
Output isn't correct |
| 12 |
Incorrect |
81 ms |
16476 KB |
Output isn't correct |
| 13 |
Incorrect |
68 ms |
17884 KB |
Output isn't correct |
| 14 |
Incorrect |
73 ms |
15944 KB |
Output isn't correct |
| 15 |
Incorrect |
70 ms |
16688 KB |
Output isn't correct |
| 16 |
Incorrect |
68 ms |
16560 KB |
Output isn't correct |
| 17 |
Incorrect |
95 ms |
19332 KB |
Output isn't correct |
| 18 |
Incorrect |
84 ms |
19332 KB |
Output isn't correct |
| 19 |
Incorrect |
97 ms |
19336 KB |
Output isn't correct |
| 20 |
Incorrect |
52 ms |
18912 KB |
Output isn't correct |
