#include <bits/stdc++.h>
using namespace std;
#define ar array
#define ll long long
const int MAX_N = 2e4 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
int n, nxt[MAX_N], vis[MAX_N], dp[MAX_N], s_chain, m_chain;
bool cycle;
vector<int> adj;
void dfs(int u) {
if (u == -1) return;
if (vis[u]) {
cycle = true;
return;
}
vis[u] = 1;
dp[u] = 0;
s_chain++;
dfs(nxt[u]);
}
int dfs2(int u) {
if (u == -1) return 0;
if (u == 0 || (vis[u] == 1 && cycle) || vis[u] == 2) return -INF;
if (dp[u] != -1) return dp[u];
vis[u] = 2;
return dp[u] = dfs2(nxt[u]) + 1;
}
void solve() {
cin >> n;
for (int i = 0; i < n; i++) cin >> nxt[i];
if (nxt[0] == 0) {
cout << 1 << "\n";
return;
}
memset(dp, -1, sizeof dp);
dfs(0);
for (int i = 0; i < n; i++) {
if (!vis[i]) {
m_chain = max(m_chain, dfs2(i));
}
}
cout << s_chain + m_chain << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int tc; tc = 1;
for (int t = 1; t <= tc; t++) {
// cout << "Case #" << t << ": ";
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
492 KB |
Output is correct |
2 |
Correct |
3 ms |
896 KB |
Output is correct |
3 |
Correct |
2 ms |
620 KB |
Output is correct |
4 |
Correct |
3 ms |
620 KB |
Output is correct |
5 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |