Submission #375384

#	Time	Username	Problem	Language	Result	Execution time	Memory
375384		gustason	Fire drill (LMIO18_sauga)	C++14	64.30 / 100	953 ms	3092 KiB

sauga

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

//mt19937 rnd(time(NULL));

const int maxN = 1005;
int best = 0;
vector<int> ans, seq, order;
int t, n, S;
vector<int> adj[maxN];
vector<char> col;
vector<bool> ok;
void dfs(int v) {
    if (!ok[v]) return;

    col[v] = '1';
    for(int u : adj[v]) {
        if (!ok[u]) continue;
//        cout << v << "-> " << u << " " << col[u] << "\n";
        if (col[u] == '0') {
            dfs(u);
        } else if (col[u] == '1') {
            ok[v] = false;
            return;
        }
    }
    col[v] = '2';
    seq.push_back(v);
}
void solve() {
    for(int i = 0; i <= n; i++) {
        random_shuffle(adj[i].begin(), adj[i].end());
    }
    random_shuffle(order.begin(), order.end());

    vector<int>().swap(seq);
    for(int i = 0; i <= n; i++) {
        col[i] = '0';
        ok[i] = true;
    }

    for(int i : order) {
//        cout << i << " ";
        if (col[i] == '0')
            dfs(i);
    }
//    cerr << "\n";

    vector<int> curr;
    for(int i = 1; i <= n; i++) {
        if (!ok[i])
            curr.push_back(i);
    }
//    for(int i : curr) {
//        cout << i << " ";
//    } cout << "\n";
    int good = n - (int) curr.size();
    if (good <= best) return;

    for(int i : seq) {
        curr.push_back(i);
    }

//    cout << good << "\n";
    ans = curr;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    srand(time(NULL));
    cin >> t >> n >> S;
    order.resize(n);
    col.resize(n+1);
    ok.resize(n+1);
    iota(order.begin(), order.end(), 1);
    for(int i = 0; i < n; i++) {
        int m;
        cin >> m;
        for(int j = 0; j < m; j++) {
            int x;
            cin >> x;
            adj[i+1].push_back(x);
        }
    }

    clock_t beg = clock();
    while((double) (clock() - beg) / CLOCKS_PER_SEC < 0.9) {
        solve();
    }
    for(int i : ans) {
        cout << i << "\n";
    }
    return 0;
}

• Subtask 1: 64.30327165735 / 100