Submission #137376

# Submission time Handle Problem Language Result Execution time Memory
137376 2019-07-27T14:29:09 Z beso123 Special graph (IZhO13_specialg) C++14
0 / 100
18 ms 5368 KB
#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],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){
    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 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[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) && 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;
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 4 5 6 1
5
2 1 6
2 6 1
1 6
2 1 6
2 6 1

6
2 3 1 5 6 4
3
2 1 2
1 2
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: At global scope:
specialg.cpp:137:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 5368 KB Output isn't correct
2 Halted 0 ms 0 KB -