Submission #1229532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229532		papaulo	Forensic (NOI12_forensic)	C++20	25 / 25	6 ms	2632 KiB

forensic

#include <bits/stdc++.h>
using namespace std;

#define MAXN 20200
int breadth[MAXN];
vector<int> rev[MAXN];
vector<int> finals;
int arr[MAXN];
int visited[MAXN];
set<pair<int, int>> st;

void dfs(int v) {
    auto p=st.find({breadth[v], v});
    if(p==st.end()) return;
    st.erase(p);
    for(auto u : rev[v]) {
        dfs(u);
    }
}

int main() {
    int n;
    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> arr[i];
        if(arr[i]<0) finals.push_back(i);
        else rev[arr[i]].push_back(i);
    }
    for(int i=0;i<n;i++) breadth[i]=-1;
    queue<int> q;
    for(auto v : finals) {
        breadth[v]=1;
        q.push(v);
    }
    while(!q.empty()) {
        int v=q.front();
        q.pop();
        for(auto u : rev[v]) {
            if(breadth[u]>=0) continue;
            breadth[u]=breadth[v]+1;
            q.push(u);
        }
    }
    st.insert({0, -1});
    for(int i=0;i<n;i++) st.insert({breadth[i], i});
    int v=0;
    int cur=0;
    int ans=0;
    memset(visited, 0, sizeof(visited));
    while(v!=-1&&!visited[v]) {
        visited[v]=1;
        dfs(v);
        cur++;
        auto p=st.end();
        p--;
        ans=max(ans, cur+p->first);
        v=arr[v];
    }
    cout << ans << endl;
    return 0;
}

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