oj.uz

답안 #731776

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
731776 2023-04-28T01:00:34 Z Trunkty 연결리스트 수사하기 (NOI12_forensic) C++14
10 / 25
 8 ms 2900 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){
            for(int i:roads[curr]){
                maxi = max(maxi,dfs(i));
            }
            if(curr==-1){
                break;
            }
            curr = arr[curr];
        }
        cout << cnt+maxi << "\n";
    }
    else{
        cout << cnt+dfs(-1)-1LL << "\n";
    }
	return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 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 2 ms 596 KB Output is correct

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 2 ms 456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 852 KB Output is correct
2 Incorrect 8 ms 2900 KB Output isn't correct
3 Halted 0 ms 0 KB -