Submission #137932

#	Time	Username	Problem	Language	Result	Execution time	Memory
137932		beso123	Special graph (IZhO13_specialg)	C++14	100 / 100	554 ms	28140 KiB

specialg

#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 (stderr)

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++)
             ~^~~~~~~~~~~

• Subtask 1: 100 / 100