Submission #731778

#	Time	Username	Problem	Language	Result	Execution time	Memory
731778		Trunkty	Forensic (NOI12_forensic)	C++14	25 / 25	8 ms	2776 KiB

forensic

#include <bits/extc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n;
int arr[20005];
bool vis[20005];
map<int,vector<int>> roads;

int dfs(int x){
    if(vis[x]){
        return -1;
    }
    int ret=0;
    for(int i:roads[x]){
        ret = max(ret,dfs(i));
    }
    return ret+1;
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> arr[i];
        roads[arr[i]].push_back(i);
    }
    int cnt=0,curr=0;
    while(1){
        if(curr==-1 or vis[curr]){
            break;
        }
        cnt++;
        vis[curr] = true;
        curr = arr[curr];
    }
    if(curr==-1){
        curr = 0;
        int maxi=0;
        while(1){
            curr = arr[curr];
            for(int i:roads[curr]){
                maxi = max(maxi,dfs(i));
            }
            if(curr==-1){
                break;
            }
        }
        cout << cnt+maxi << "\n";
    }
    else{
        cout << cnt+dfs(-1)-1LL << "\n";
    }
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 10 / 10