Submission #713642

#	Time	Username	Problem	Language	Result	Execution time	Memory
713642		aedmhsn	Forensic (NOI12_forensic)	C++17	10 / 25	4 ms	724 KiB

forensic

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 10