Submission #425437

#	Time	Username	Problem	Language	Result	Execution time	Memory
425437		errorgorn	Forensic (NOI12_forensic)	C++17	25 / 25	6 ms	1996 KiB

forensic

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int n,arr[20005],loop[20005],val[20005];
bool check[20005];
vector<int> v[20005],mv;
void print(){
  for (int x=0;x<n;x++){
    printf("%d ",check[x]);
  }
  printf("\n");
}
void print2(){
    printf("loop: ");
  for (int x=0;x<n;x++){
    printf("%d ",loop[x]);
  }
  printf("\n");
}
void print3(){
    for (int x=0;x<n;x++){
        printf("%d ",val[x]);
    }
    printf("\n");
}
void backtrack(int i){
    for (vector<int>::iterator it=v[i].begin();it!=v[i].end();it++){
        if (loop[*it]==0){
            check[*it]=true;
            backtrack(*it);
        }
    }
}
void backtrack2(int i){
    for (vector<int>::iterator it=v[i].begin();it!=v[i].end();it++){
        if (loop[*it]==0){
            check[*it]=false;
            backtrack2(*it);
        }
    }
}
void loop_find(int i){
    check[i]=true;
    while (arr[i]!=-1 && !check[arr[i]]){
        i=arr[i];
        check[i]=true;
    }
    if (arr[i]==-1){
        backtrack(i);
    }
    else if (arr[i]==i){
        loop[i]=-1;
        backtrack(i);
        loop[i]=0;
    }
    else{
        while (loop[arr[i]]==0){
            loop[arr[i]]=loop[i]+1;
            i=arr[i];
        }
        backtrack(i);
        loop[i]--;
        while (loop[arr[i]]<loop[i]){
            loop[arr[i]]=loop[i];
            i=arr[i];
            backtrack(i);
        }
        backtrack(arr[i]);
    }
}
int get_val(int i){
    if (val[i]!=0) return val[i];
    else if (v[i].size()==0) return val[i]=1;
    else{
        int ans=0;
        for (vector<int>::iterator it=v[i].begin();it!=v[i].end();it++){
            if (loop[*it]==0 && arr[i]!=i) ans=max(ans,get_val(*it)+1);
        }
        return val[i]=ans;
    }
}
void ex(int i){
    int j=val[i];
    vector<int>::iterator it;
    while ((--j)!=0){
        check[i]=false;
        for (it=v[i].begin();val[*it]!=j;it++);
        i=*it;
    }
    check[i]=false;
}
int main(){
  int t,k=0;
  //freopen("input.txt","r",stdin);
  scanf("%d",&n);
  for (int x=0;x<n;x++){
    scanf("%d",&t);
    arr[x]=t;
    if (t!=-1) v[t].push_back(x);
    else mv.push_back(x);
  }
  //check for loops
  for (int x=0;x<n;x++){
    if (!check[x]){
        loop_find(x);
    }
  }
  if (mv.size()==0){
      int i=0,j=1;
      while (arr[i]!=i && loop[i]==0){
        i=arr[i];
        j++;
      }
      printf("%d\n",j+loop[i]);
  }
  else{
    memset(check,false,sizeof(check));
    for (vector<int>::iterator it=mv.begin();it!=mv.end();it++){
        check[*it]=true;
        backtrack(*it);
    }
    backtrack2(0);
    int i=0,j=1;
    loop[i]=-1;
    while (arr[i]!=-1 && loop[arr[i]]!=-1){
        i=arr[i];
        loop[i]=-1;
        j++;
    }
    for (int x=0;x<n;x++){
        if (check[x] && loop[x]!=-1) k=max(k,get_val(x));
    }
    //printf("%d %d\n",j,k);
    printf("%d\n",j+k);
  }
}

Compilation message (stderr)

forensic.cpp: In function 'int main()':
forensic.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
forensic.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     scanf("%d",&t);
      |     ~~~~~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 10 / 10