Submission #520174

#	Time	Username	Problem	Language	Result	Execution time	Memory
520174		_martynas	Fire drill (LMIO18_sauga)	C++11	71.63 / 100	664 ms	5956 KiB

sauga

#include <bits/stdc++.h>

using namespace std;

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

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()
{
    if(NodesLeft.empty()) return;
    memset(Heat, 0, sizeof(Heat));
    vector<int> pool;
    for(int x : NodesLeft) pool.push_back(x);
    for(int k = 0; k < MAX_RUNS; k++) {
        int u = pool[rand() % pool.size()];
        for(int i = 0; i < RUN_LENGTH; i++) {
            if(Adj[u].empty()) break;
            Heat[u]++;
            u = Adj[u][rand()%Adj[u].size()];
        }
    }
    Priority = pool;
    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;
            v--;
            Adj[u].push_back(v);
            RevAdj[v].push_back(u);
            in[v]++, out[u]++;
        }
        NodesLeft.insert(u);
    }

    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;
    int cnt = 0;

//    for(int i = 0; i < n; i++) {
//        cerr << Heat[i] << " ";
//    }
//    cerr << "\n";
//    for(int i = 0; i < n; i++) {
//        cerr << Priority[i] << " ";
//    }
//    cerr << "\n";

    run:

    while(!Take.empty()) {
        int u = Take.front();
        Take.pop();
        if(in[u] == 0) {
            //cerr << "end: " << u << "\n";
            End.push_back(u);
        }
        else {
            //cerr << "start: " << u << "\n";
            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);
            }
        }
    }

    // recompute heat every other run
    if(cnt % 8 == 0) {
        PrepHeatPriority();
        idx = 0;
    }
    cnt++;

    if(!NodesLeft.empty()) {
        do {
            while(!NodesLeft.count(Priority[idx])) idx++;
            int u = Priority[idx];
            NodesLeft.erase(u);
            //cerr << "rem: " << u << "\n";
            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: 71.63489257724 / 100