#include <bits/stdc++.h>
using namespace std;
int n,arr[20001];
bool vis[20001],vis2[20001];
int maxi[20001];
vector<int> brr;
bool loop;
void dfs(int cur){
if (cur==-1) return;
if (vis[cur]){
loop=true;
return;
}
vis[cur]=true;
maxi[cur]=0;
brr.push_back(cur);
dfs(arr[cur]);
}
int dfs2(int cur){
if (cur==-1) return 0;
if ((vis[cur] && loop) || cur==0) return -1e9;
if (maxi[cur]!=-1) return maxi[cur];
if (vis2[cur]) return -1e9;
vis2[cur]=true;
maxi[cur]=dfs2(arr[cur])+1;
return maxi[cur];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for (int i=0;i<n;i++) cin>>arr[i];
if (arr[0]==0){
cout<<1;
return 0;
}
memset(maxi,-1,sizeof(maxi));
dfs(0);
int ans=0;
for (int i=0;i<n;i++){
if (!vis[i]){
ans=max(ans,dfs2(i));
}
}
cout<<brr.size()+ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
428 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
5 |
Correct |
3 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
632 KB |
Output is correct |
3 |
Correct |
4 ms |
632 KB |
Output is correct |
4 |
Correct |
5 ms |
1404 KB |
Output is correct |
5 |
Correct |
3 ms |
760 KB |
Output is correct |