#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],pt[100005],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,p,tin,tout,H;
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,int p){
used[v]=1;
H[v]=h;
tin[v]=timer++;
if(cyc[v]==0){
if(cyc[p]!=0)
pt[v]=p;
else pt[v]=pt[p];
}
for(int k=0;k<r[v].size();k++){
int to=r[v][k];
if(used[to]==0)
DFS2(to,h+1,v);
}
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 dist(int a1,int b1){
///cout<<a1<<' '<<b1<<' '<<cyc[a1]<<' '<<cyc[b1]<<' '<<yes(b1,a1)<<endl;
if(fs(a1)!=fs(b1))
return -1;
if(cyc[a1]==cyc[b1] && fs(a1)==fs(b1) && cyc[a1]!=0){
if(yes(b1,a1)){
if(c[a1]<c[b1]){
if(get(c[b1]-1)-get(c[a1]-1)==0)
return abs(H[a1]-H[b1]);
else return -1;
}
else{
if(get(c[b1]-1)-get(c[bebi[cyc[a1]]]-1)==0 && get(c[bebi[cyc[a1]]]+Size[cyc[a1]]-1)-get(c[a1]-1)==0){
return abs(H[a1]-H[b1]);
}
else return -1;
}
}
else{
if(c[a1]<c[b1]){
if(get(c[b1]-1)-get(c[a1]-1)==0)
return Size[cyc[a1]]-abs(H[a1]-H[b1]);
else return -1;
}
else{
if(get(c[b1]-1)-get(c[bebi[cyc[a1]]]-1)==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)){
if(cyc[a1]==0 && cyc[b1]!=0 && pt[a1]!=b1){
int aa=dist(a1,pt[a1]),bb=dist(pt[a1],b1);
if(aa!=-1 && bb!=-1)
return aa+bb;
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 && pt[a1]!=b1){
int aa=dist(a1,pt[a1]),bb=dist(pt[a1],b1);
if(aa!=-1 && bb!=-1)
return aa+bb;
else return -1;
}
else return 0-1;
}
else return -1;
}
return -1;
}
main(){
cin>>n;
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,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;
return 0;
}
/*
10
2 3 4 5 6 1 5 2 8 8
6
1 4
1 5
2 9 1
2 10 4
2 1 5
2 7 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, long long int)':
specialg.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<r[v].size();k++){
~^~~~~~~~~~~~
specialg.cpp: At global scope:
specialg.cpp:148:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
5496 KB |
Output is correct |
| 2 |
Correct |
18 ms |
5496 KB |
Output is correct |
| 3 |
Correct |
20 ms |
5496 KB |
Output is correct |
| 4 |
Correct |
41 ms |
5640 KB |
Output is correct |
| 5 |
Correct |
24 ms |
5496 KB |
Output is correct |
| 6 |
Correct |
83 ms |
6280 KB |
Output is correct |
| 7 |
Correct |
85 ms |
6400 KB |
Output is correct |
| 8 |
Correct |
85 ms |
6380 KB |
Output is correct |
| 9 |
Correct |
83 ms |
6400 KB |
Output is correct |
| 10 |
Correct |
85 ms |
6512 KB |
Output is correct |
| 11 |
Correct |
494 ms |
29920 KB |
Output is correct |
| 12 |
Correct |
466 ms |
19900 KB |
Output is correct |
| 13 |
Correct |
488 ms |
23292 KB |
Output is correct |
| 14 |
Correct |
459 ms |
18708 KB |
Output is correct |
| 15 |
Correct |
467 ms |
20456 KB |
Output is correct |
| 16 |
Correct |
464 ms |
19992 KB |
Output is correct |
| 17 |
Correct |
522 ms |
26832 KB |
Output is correct |
| 18 |
Correct |
514 ms |
26884 KB |
Output is correct |
| 19 |
Correct |
536 ms |
26860 KB |
Output is correct |
| 20 |
Correct |
495 ms |
30156 KB |
Output is correct |
