Submission #172527

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
172527	2020-01-01T20:31:06 Z	RafaelSus	Special graph (IZhO13_specialg)	C++14	0 / 100	1000 ms	10108 KB

specialg

#include <bits/stdc++.h>
 
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);

int n,a[N];
vector<int>g[N];
int to[N],out[N];
int mark[N];

vector<int>tr[N];
vector<int>gagat;
int comp[N];
int cic[N];

void dfs(int v,vector<int>&tmp){
  tmp.pb(v);
  mark[v]=1;
  if(to[v]){
    if(mark[g[v][0]]==1){
      cic[v]=1;
      int h=g[v][0];
      for(int i=tmp.size()-1;i>=0;--i){
        if(tmp[i]==g[v][0])break;
        tr[h].pb(tmp[i]+n);
        h=tmp[i]+n;
      }
      gagat.pb(v);
    }else if(mark[g[v][0]]==2){
      int h=g[v][0];
      for(int i=tmp.size()-1;i>=0;--i){
        tr[h].pb(tmp[i]);
        h=tmp[i];
      }
      if(cic[g[v][0]]){
        int h=g[v][0]+n;
        for(int i=tmp.size()-1;i>=0;--i){
          tr[h].pb(tmp[i]+n);
          h=tmp[i]+n;
        }
      }
    }else{
      dfs(g[v][0],tmp);
      tr[g[v][0]].pb(v);
    }
  }else{
    gagat.pb(v);
  }
  mark[v]=2;
}

int tin[N],tout[N],timer;
int depth[N],comp_num,sz[N];
int anc[N];

void dfs_tree(int v,int p,int d,int comp_num,int vv){
  anc[v]=vv;
  tin[v]=++timer;
  depth[v]=d;
  comp[v]=comp_num;
  sz[v]=1;
  for(auto to:tr[v]){
    if(to!=p){
      dfs_tree(to,v,d+1,comp_num,vv);
      sz[v]+=sz[to];
    }
  }
  tout[v]=++timer;
}

void dfs0(int v,int p,int comp_num,int vv){
  if(comp[v])comp[v]=comp_num;
  else return;
  anc[v]=vv;
  sz[v]=1;
  for(auto to:tr[v]){
    if(to!=p){
      dfs0(to,v,comp_num,vv);
      sz[v]+=sz[to];
    }
  }
}

bool upper(int a,int b){
  return tin[a]<=tin[b]&&tout[a]>=tout[b];
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);

  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    if(a[i]){
      g[i].pb(a[i]);
      to[i]=1;
      out[a[i]]++;
    }
  }
  
  for(int i=1;i<=n;i++){
    if(out[i]==0){
      vector<int>tmp;
      dfs(i,tmp);
    }
  }
  ///////////////
  /*for(int i=1;i<=2*n;i++){
    cout<<i<<":          ";
    for(int j=0;j<tr[i].size();j++){
      cout<<tr[i][j]<<' ';
    }
    cout<<'\n';
  }*/
  ///////////////
  for(int i=0;i<gagat.size();i++){
    int v=gagat[i];
    timer=0;
    comp_num++;
    dfs_tree(v,v,1,comp_num,v);
  }
  
  int q;
  cin>>q;
  while(q-->0){
    int type;
    cin>>type;
    if(type==1){
      int v;
      cin>>v;
      int to=g[v][0];
      int sec=v+n;
      if(sz[anc[v]]-sz[v]>sz[v]){
        comp_num++;
        dfs0(v,v,comp_num,v);
      }else{
        comp_num++;
        dfs0(v,v,comp_num,v);
      }
      if(comp[sec]){
        int h=sec;
        while(1){
          comp[h]=0;
          if(tr[h].size()==0)break;
          else h=tr[h][0];
        }
      }
    }else{
      int a,b;
      cin>>a>>b;
      if(comp[a]!=comp[b]){
        cout<<"-1\n";
      }else{
        if(upper(b,a)){
          cout<<depth[a]-depth[b]<<'\n';
        }else if(comp[a+n]==comp[b]){
          if(upper(b,a+n)){
            cout<<depth[a+n]-depth[b]<<'\n';
          }else{
            cout<<"-1\n";
          }
        }else{
          cout<<"-1\n";
        }
      }
    }
  }
}

Compilation message

specialg.cpp: In function 'int main()':
specialg.cpp:121:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<gagat.size();i++){
               ~^~~~~~~~~~~~~
specialg.cpp:136:11: warning: unused variable 'to' [-Wunused-variable]
       int to=g[v][0];
           ^~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1073 ms	10108 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-