81562024-01-12 14:50:03ZsBalazsTitkos sorozatcpp17Runtime error 35/40201ms130812 KiB
#include <bits/stdc++.h>
using namespace std;

vector<vector<long long>> graph;
vector<long long> megoldas;
vector<long long> mutat;
vector<bool> volt;

void bejar(long long current) {
    if (volt[current]) return;
    
    volt[current] = true;
    
    for (long long szom : graph[current]) {
        if (megoldas[szom] < megoldas[current]+1) {
            megoldas[szom] = megoldas[current]+1;
        }
        mutat[szom]--;
    }
}

int main() {
    long long n;
    cin >> n;
    
    graph.resize(n);
    megoldas.assign(n, 0);
    mutat.assign(n, 0);
    volt.assign(n, false);
    
    for (long long i = 0; n > i; i++) {
        long long temp;
        cin >> temp;
        
        if (temp != -1) {
            temp--;
            
            mutat[temp]++;
            graph[i].push_back(temp);
            
            for (long long j = i+1; temp > j; j++) {
                mutat[i]++;
                graph[j].push_back(i);
            }
        } else {
            for (long long j = i+1; n > j; j++) {
                graph[j].push_back(i);
                mutat[i]++;
            }
        }
    }
    
    long long counter = 0;
    while (counter < n) {
        for (long long i = 0; n > i; i++) {
            if (mutat[i] == 0 && !volt[i]) {
                bejar(i);
                counter++;
            }
        }   
    }
    
    // megoldas, index
    vector<pair<long long, long long>> sor;
    
    for (long long i = 0; n > i; i++) {
        sor.push_back({megoldas[i], i});
    }
    
    sort(sor.begin(), sor.end());
    
    vector<long long> ans(n, 0);
    
    long long next = 1;
    for (long long i = 0; n > i; i++) {
        long long index = sor[i].second;
        
        ans[index] = next;
        
        next++;
    }
    
    for (long long a : ans) {
        cout << a << " ";
    }
    cout << endl;
    
	return 0;
}
SubtaskSumTestVerdictTimeMemory
base35/40
1Accepted0/03ms1940 KiB
2Accepted0/048ms13504 KiB
3Accepted1/13ms2272 KiB
4Accepted1/13ms2360 KiB
5Accepted2/23ms2760 KiB
6Accepted1/14ms3360 KiB
7Accepted1/13ms3420 KiB
8Accepted2/24ms3820 KiB
9Accepted2/2130ms42688 KiB
10Runtime error0/2164ms130812 KiB
11Accepted2/2108ms32104 KiB
12Accepted2/2100ms28808 KiB
13Accepted2/297ms27780 KiB
14Accepted2/294ms26372 KiB
15Accepted2/293ms24668 KiB
16Accepted3/389ms24408 KiB
17Accepted3/389ms24116 KiB
18Accepted3/389ms23780 KiB
19Accepted3/385ms23308 KiB
20Accepted3/375ms22568 KiB
21Runtime error0/1189ms130208 KiB
22Runtime error0/1189ms130180 KiB
23Runtime error0/1201ms130176 KiB