This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
| ~~~~~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |