제출 #713646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713646		aedmhsn	연결리스트 수사하기 (NOI12_forensic)	C++17	10 / 25	5 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];

bool cycled=0;

ll dfs(int node){
    if(dp[node] != -1)
        return dp[node];
    if(path1[node]){
        return (cycled ? -INT_MAX: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)
        cycled=true;
    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