#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n,a[100005],cnt=0,qq[100005],d=1,b=0,c[100005],kd[100005],cyc[100005],bb=1,viz[100005],bebi[100005],timer=0,Size[100005],par[100005];
vector <int> g[100005],r[100005];
vector <int> starts,used,tin,tout,H,p;
vector <pii> all;
void DFS1(int v){
used[v]=b;
p.push_back(v);
c[v]=p.size()-1;
for(int k=0;k<g[v].size();k++){
int to=g[v][k];
if(used[to]==0)
DFS1(to);
else{
if(used[to]==b){
a[c[to]]+=bb;
a[c[v]+1]-=bb;
bebi[bb]=to;
Size[bb]=c[v]-c[to]+1;
bb++;
}
}
}
}
void DFS2(int v,int h){
used[v]=1;
H[v]=h;
tin[v]=timer++;
for(int k=0;k<r[v].size();k++){
int to=r[v][k];
if(used[to]==0)
DFS2(to,h+1);
}
tout[v]=timer++;
}
void UPD(int index,int val){
index=index+1;
while(index<=n){
viz[index]+=val;
index+=index&(-index);
}
}
int get(int index){
if(index<0)
return 0;
int sum=0;
index=index+1;
while(index>0){
sum+=viz[index];
index-=index&(-index);
}
return sum;
}
bool yes(int a1,int a2){
if(tin[a1]<=tin[a2] && tout[a1]>=tout[a2])
return true;
return false;
}
void ms(){
for(int k=1;k<=n;k++)
par[k]=k;
}
int fs(int v){
if(par[v]==v)
return v;
return par[v]=fs(par[v]);
}
void us(int a1,int b1){
a1=fs(a1);
b1=fs(b1);
if(a1!=b1){
par[b1]=a1;
}
}
int DFS(int v,int f){
used[v]=d;
if(v==f)
return cnt;
cnt++;
if(qq[v]!=0 && used[qq[v]]!=d)
DFS(qq[v],f);
else return -1;
}
int dist(int a1,int b1){
///cout<<a1<<' '<<b1<<' '<<fs(a1)<<' '<<fs(b1)<<' '<<yes(b1,a1)<<endl;
if(cyc[a1]==cyc[b1] && fs(a1)==fs(b1) && cyc[a1]!=0){
if(yes(b1,a1)){
if(c[b1]<c[a1])
swap(b1,a1);
if(get(c[b1])-get(c[a1])==0)
return abs(H[a1]-H[b1]);
else return -1;
}
else{
if(c[b1]>c[a1])
swap(b1,a1);
if(get(c[b1]-1)-get(c[bebi[cyc[a1]]])==0 && get(c[bebi[cyc[a1]]]+Size[cyc[a1]]-1)-get(c[a1]-1)==0)
return Size[cyc[a1]]-abs(H[a1]-H[b1]);
else return -1;
}
}
if(fs(a1)==fs(b1) && yes(b1,a1)){
return abs(H[a1]-H[b1]);
}
else{
if(fs(a1)==fs(b1)){
if(cyc[a1]==0 && cyc[b1]!=0){
int aa=dist(a1,bebi[cyc[b1]]),bb=dist(bebi[cyc[b1]],b1);
if(aa!=-1 && bb!=-1)
return aa+bb;
else return -1;
}
else
if(cyc[a1]!=0 && cyc[b1]==0){
swap(a1,b1);
int aa=dist(a1,bebi[cyc[b1]]),bb=dist(bebi[cyc[b1]],b1);
if(aa!=-1 && bb!=-1)
return aa+bb;
else return -1;
}
else return -1;
}
else return -1;
}
}
main(){
cin>>n;
if(n<=5000){
for(int k=1;k<=n;k++)
cin>>qq[k];
int q;
cin>>q;
used.resize(n+1,0);
for(int k=1;k<=q;k++){
int a;
cin>>a;
if(a==1){
int b;
cin>>b;
qq[b]=0;
}
if(a==2){
int b,c;
cin>>b>>c;
d++;
cnt=0;
cout<<DFS(b,c)<<endl;
}
}
return 0;
}
for(int k=1;k<=n;k++){
cin>>a[k];
kd[k]=a[k];
if(a[k]==0){
starts.push_back(k);
continue;
}
g[k].push_back(a[k]);
r[a[k]].push_back(k);
a[k]=0;
}
used.resize(n+1,0);
for(int k=1;k<=n;k++){
if(r[k].size()==0){
b++;
DFS1(k);
}
}
for(int k=1;k<=n;k++)
if(used[k]==0){
b++;
DFS1(k);
}
for(int k=0;k<=n;k++){
a[k]+=a[k-1];
if(a[k]!=0){
cyc[p[k]]=a[k];
}
}
int q;
cin>>q;
while(q--){
int type;
cin>>type;
if(type==1){
int lll;
cin>>lll;
if(cyc[lll]!=0){
UPD(c[lll],1);
}
kd[lll]*=-1;
all.push_back({-1,lll});
}
else{
int lll,rrr;
cin>>lll>>rrr;
all.push_back({lll,rrr});
}
}
for(int k=1;k<bb;k++){
starts.push_back(bebi[k]);
}
tin.resize(n+1,0);
tout.resize(n+1,0);
used.resize(0);
used.resize(n+1);
H.resize(n+1,0);
for(auto i : starts){
DFS2(i,0);
}
ms();
for(int k=1;k<=n;k++){
if(kd[k]>0)
us(k,kd[k]);
}
vector <int> ans;
for(int k=all.size()-1;k>=0;k--){
if(all[k].x==-1){
int op=all[k].y;
kd[op]*=-1;
us(op,kd[op]);
UPD(c[op],-1);
}
else{
int a1=all[k].x,b1=all[k].y;
ans.push_back(dist(a1,b1));
}
}
reverse(ans.begin(),ans.end());
for(auto i : ans)
cout<<i<<endl;
///for(int k=1;k<=n;k++)
///cout<<k<<' '<<c[k]<<endl;
return 0;
}
/*
6
2 3 1 5 6 4
3
2 1 2
1 1
2 2 1
*/
Compilation message
specialg.cpp: In function 'void DFS1(long long int)':
specialg.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<g[v].size();k++){
~^~~~~~~~~~~~
specialg.cpp: In function 'void DFS2(long long int, long long int)':
specialg.cpp:35:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<r[v].size();k++){
~^~~~~~~~~~~~
specialg.cpp: In function 'long long int DFS(long long int, long long int)':
specialg.cpp:84:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(v==f)
^~
specialg.cpp:86:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
cnt++;
^~~
specialg.cpp: At global scope:
specialg.cpp:134:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
specialg.cpp: In function 'long long int DFS(long long int, long long int)':
specialg.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
18 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
20 ms |
5116 KB |
Output is correct |
| 4 |
Correct |
41 ms |
5240 KB |
Output is correct |
| 5 |
Correct |
21 ms |
5112 KB |
Output is correct |
| 6 |
Correct |
97 ms |
5340 KB |
Output is correct |
| 7 |
Correct |
100 ms |
5496 KB |
Output is correct |
| 8 |
Correct |
100 ms |
5368 KB |
Output is correct |
| 9 |
Correct |
96 ms |
5368 KB |
Output is correct |
| 10 |
Correct |
101 ms |
5368 KB |
Output is correct |
| 11 |
Correct |
502 ms |
29928 KB |
Output is correct |
| 12 |
Incorrect |
490 ms |
19728 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
