oj.uz

Submission #425437

# Submission time Handle Problem Language Result Execution time Memory
425437 2021-06-13T03:55:15 Z errorgorn Forensic (NOI12_forensic) C++17
25 / 25
 6 ms 1996 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 760 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 2 ms 844 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 756 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 2 ms 844 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1100 KB Output is correct
2 Correct 5 ms 1412 KB Output is correct
3 Correct 4 ms 1100 KB Output is correct
4 Correct 6 ms 1996 KB Output is correct
5 Correct 4 ms 1228 KB Output is correct