Submission #1168949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168949		hamzabc	Forensic (NOI12_forensic)	C++20	15 / 25	3 ms	2116 KiB

forensic

#include <bits/stdc++.h>

using namespace std;
 
 
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'


long long int N;
vector<int> forwrd;
vector<vector<int>> backwrd;
vector<int> vis;
vector<int> len;
vector<int> nd;


void dfs(int n){
    if (vis[n])
        return;
    vis[n] = true;
    for (auto k : backwrd[n]){
        len[k] = len[n] + 1;
        dfs(k);
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    len.resize(N, -1);
    vis.resize(N);
    forwrd.resize(N);
    backwrd.resize(N);
    for (int i = 0; i < N; i++){
        cin >> forwrd[i];
        if (forwrd[i] == -1){
            nd.push_back(i);
            len[i] = 0;
        }else
            backwrd[forwrd[i]].push_back(i);
    }
    for (auto k : nd)
        dfs(k);
    multiset<int> que;
    for (int i = 0; i < N; i++)
        que.insert(-len[i]);
    int ret = max(0, len[0]);
    if (len[0] == -1){
        fill(all(vis), false);
        int j = 1, u = 0;
        while (vis[forwrd[u]] == 0){
            vis[u] = true;
            j++;
            u = forwrd[u];
            vis[u] = true;
        }
        ret = j + -*que.begin() + 1;
    }else{
        fill(all(vis), 0);
        int j = 1, u = 0;
        while (true){
            stack<int> stc;
            stc.push(u);
            vis[u] = true;
            while (stc.size()){
                int f = stc.top();
                stc.pop();
                que.erase(que.find(-len[f]));
                for (auto k : backwrd[f])
                    if (vis[k] == 0){
                        vis[k] = true;
                        stc.push(k);
                    }
            }
            j++;
            if (que.size())
                ret = max(ret, j + -*que.begin());
            if (forwrd[u] == -1)
                break;
            u = forwrd[u];
        }
    }
    cout << ret;
}

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