#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){
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(int k=0;k<ans.size();k++)
cout<<ans[k]<<endl;
return 0;
}
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:147:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
specialg.cpp: In function 'int main()':
specialg.cpp:229:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<ans.size();k++)
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
5368 KB |
Output is correct |
| 2 |
Correct |
19 ms |
5500 KB |
Output is correct |
| 3 |
Correct |
20 ms |
5496 KB |
Output is correct |
| 4 |
Correct |
41 ms |
5640 KB |
Output is correct |
| 5 |
Correct |
22 ms |
5496 KB |
Output is correct |
| 6 |
Correct |
84 ms |
6148 KB |
Output is correct |
| 7 |
Correct |
84 ms |
6148 KB |
Output is correct |
| 8 |
Correct |
85 ms |
6192 KB |
Output is correct |
| 9 |
Correct |
84 ms |
6088 KB |
Output is correct |
| 10 |
Correct |
88 ms |
6252 KB |
Output is correct |
| 11 |
Correct |
505 ms |
27868 KB |
Output is correct |
| 12 |
Correct |
465 ms |
18280 KB |
Output is correct |
| 13 |
Correct |
503 ms |
21292 KB |
Output is correct |
| 14 |
Correct |
457 ms |
17000 KB |
Output is correct |
| 15 |
Correct |
469 ms |
18792 KB |
Output is correct |
| 16 |
Correct |
466 ms |
18272 KB |
Output is correct |
| 17 |
Correct |
511 ms |
24868 KB |
Output is correct |
| 18 |
Correct |
554 ms |
24848 KB |
Output is correct |
| 19 |
Correct |
522 ms |
24784 KB |
Output is correct |
| 20 |
Correct |
494 ms |
28140 KB |
Output is correct |
