Submission #520165

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
520165	2022-01-28T16:01:13 Z	_martynas	Fire drill (LMIO18_sauga)	C++11	10 / 100	168 ms	5868 KB

sauga

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1005;
const int MAX_RUNS = 1000;
const int RUN_LENGTH = 100;

int t, n, s;
vector<int> Remove;
vector<int> Start, End;
vector<int> Adj[MAX_N];
vector<int> RevAdj[MAX_N];
int Heat[MAX_N];
int in[MAX_N], out[MAX_N];
set<int> NodesLeft;
vector<int> Priority;

bool removeIn(int i)
{
    in[i]--;
    return in[i] == 0;
}

bool removeOut(int i)
{
    out[i]--;
    return out[i] == 0;
}

void PrepHeatPriority()
{
    for(int k = 0; k < MAX_RUNS; k++) {
        int u = rand() % n;
        for(int i = 0; i < RUN_LENGTH; i++) {
            if(Adj[u].empty()) break;
            Heat[u]++;
            u = Adj[u][rand()%Adj[u].size()];
        }
    }
    Priority = vector<int>(n);
    iota(Priority.begin(), Priority.end(), 0);
    sort(Priority.begin(), Priority.end(),
    [&](int i, int j)
    {
        return Heat[i] > Heat[j];
    });
}

int main()
{
    cin >> t >> n >> s;
    for(int u = 0; u < n; u++) {
        int k;
        cin >> k;
        for(int i = 0; i < k; i++) {
            int v;
            cin >> v;
            Adj[u].push_back(v);
            RevAdj[v].push_back(u);
            in[v]++, out[u]++;
        }
        NodesLeft.insert(u);
    }

    PrepHeatPriority();

    queue<int> Take;
    for(int u = 0; u < n; u++) {
        if(in[u] == 0 || out[u] == 0) {
            NodesLeft.erase(u);
            Take.push(u);
        }
    }

    int idx = 0;

    run:
    while(!Take.empty()) {
        int u = Take.front();
        Take.pop();
        if(in[u] == 0) {
            End.push_back(u);
        }
        else {
            Start.push_back(u);
        }
        for(int v : Adj[u]) {
            if(!NodesLeft.count(v)) continue;
            bool add = removeIn(v);
            if(add) {
                NodesLeft.erase(v);
                Take.push(v);
            }
        }
        for(int v : RevAdj[u]) {
            if(!NodesLeft.count(v)) continue;
            bool add = removeOut(v);
            if(add) {
                NodesLeft.erase(v);
                Take.push(v);
            }
        }
    }
    if(!NodesLeft.empty()) {
        do {
            while(!NodesLeft.count(Priority[idx])) idx++;
            int u = Priority[idx];
            Remove.push_back(u);
            for(int v : Adj[u]) {
                if(!NodesLeft.count(v)) continue;
                bool add = removeIn(v);
                if(add) {
                    NodesLeft.erase(v);
                    Take.push(v);
                }
            }
            for(int v : RevAdj[u]) {
                if(!NodesLeft.count(v)) continue;
                bool add = removeOut(v);
                if(add) {
                    NodesLeft.erase(v);
                    Take.push(v);
                }
            }
        }
        while(Take.empty() && !NodesLeft.empty());

        goto run;
    }

    cerr << "Removing\n";
    for(int x : Remove) {
        cout << 1+x << "\n";
    }
    cerr << "----------\n";
    for(int x : Start) {
        cout << 1+x << "\n";
    }
    cerr << "----------\n";
    reverse(End.begin(), End.end());
    for(int x : End) {
        cout << 1+x << "\n";
    }

    return 0;
}
/*
-1 3 0
2 2 3
1 3
0

0 4 1
2 2 3
0
1 4
1 1
*/

Subtask #1

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	5668 KB	Output is correct
2	Incorrect	2 ms	460 KB	Output is not a permutation
3	Incorrect	3 ms	460 KB	Output is not a permutation
4	Incorrect	6 ms	460 KB	Output is not a permutation
5	Incorrect	5 ms	460 KB	Output is not a permutation
6	Incorrect	5 ms	460 KB	Output is not a permutation
7	Incorrect	29 ms	1248 KB	Output is not a permutation
8	Incorrect	168 ms	5868 KB	Output is not a permutation
9	Incorrect	23 ms	964 KB	Output is not a permutation
10	Incorrect	3 ms	460 KB	Output is not a permutation