oj.uz

Submission #731778

# Submission time Handle Problem Language Result Execution time Memory
731778 2023-04-28T01:02:26 Z Trunkty Forensic (NOI12_forensic) C++14
25 / 25
 8 ms 2776 KB 
#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.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 464 KB Output is correct
2 Correct 1 ms 460 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 596 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 5 ms 1876 KB Output is correct
3 Correct 7 ms 2264 KB Output is correct
4 Correct 8 ms 2776 KB Output is correct
5 Correct 8 ms 1484 KB Output is correct