oj.uz

Submission #713642

# Submission time Handle Problem Language Result Execution time Memory
713642 2023-03-22T17:54:42 Z aedmhsn Forensic (NOI12_forensic) C++17
10 / 25
 4 ms 724 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a)) 
 
#define boost() ios_base::sync_with_stdio(false); cin.tie(0)
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
 
const int mxN=2e4+5;

ll dp[mxN], a[mxN];
bool path1[mxN], tvis[mxN];

ll dfs(int node){
    if(dp[node] != -1)
        return dp[node];
    if(path1[node])
        return 0;
    tvis[node]=1;
    int ret=0;
    if(a[node] == -1)
        ret = 1;
    if(tvis[a[node]])
        ret = -INT_MAX;
    else
        ret = dfs(a[node])+1;
    tvis[node]=0;
    return dp[node]=ret;
}


int main(){
    ms(dp, -1);
    ll n, lnode=0, ans=0, ans1=0;
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> a[i];
    while(lnode != -1 && !path1[lnode]){
        path1[lnode]=1;
        ans++;
        lnode = a[lnode];
    }
    if(lnode != -1){
        cout << ans;
    }
    else{
        for(int i=0; i<n; i++){
            if(dp[i] == -1){
                dfs(i);
            }
            ans1 = max(ans1, dp[i]);
        }
        cout << ans+ans1;
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Incorrect 4 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -