Submission #451296

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
451296	2021-08-03T07:10:20 Z	Aldas25	Fire drill (LMIO18_sauga)	C++14	47.7684 / 100	837 ms	52740 KB

sauga

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1000100, MAXK = 60;
//const ll MOD = 998244353;
const ll MOD = 1e9+7;
const ll INF = 1e17;

int t, n, s;
vi adj[MAXN];
int deg[MAXN];
vi mustBef[MAXN];

vi ans;
int best = 1e9;

bool wasEvaced[MAXN];

void eval (vi seq) {
    FOR(i, 1, n) wasEvaced[i] = false;

    int cur = 0;
    for (int x : seq) {
            bool bad = false;
        for (int u : mustBef[x])
            if (!wasEvaced[u]) bad = true;
        wasEvaced[x] = true;
        cur += bad;
    }


    //cout << " evaled, best was = " << best << " cur is = " << cur << endl;

    if (cur < best) {
        best = cur;
        swap(seq, ans);
    }
}

bool checked[MAXN];

//set<int> rem;

void topo1 () {
    FOR(i, 1, n) checked[i] = false;

    queue<int> q;
    vi seq;
    while ((int)seq.size() < n) {
        int mnDeg = n+1;
        int ch = 1;
        FOR(i, 1, n) {
            if (checked[i]) continue;
            if (deg[i] < mnDeg) {
                ch = i;
                mnDeg = deg[i];
            } else if (deg[i] == 0) {
                q.push(i);
            }
        }

        q.push(ch);

        while (!q.empty()) {
            int v = q.front();
           // cout << " v = " << v<< endl;
            seq.pb(v);
            checked[v] = true;
            q.pop();

            for (int u : adj[v]) {
                deg[u]--;
                if (deg[u]==0 && !checked[u])
                    q.push(u);
            }
        }
    }

    eval(seq);
}

void topo2 () {
    FOR(i, 1, n) checked[i] = false;

    queue<int> q;
    vi seq;
    while ((int)seq.size() < n) {
        FOR(i, 1, n) if (!checked[i] && deg[i] == 0)
            q.push(i);

        if (q.empty()) {
            int cnt = n - (int)seq.size();
            int rn = rng() % cnt + 1;
            int ch = 1;
            FOR(i, 1, n) {
                if (checked[i]) continue;
                rn--;
                if (rn == 0) {
                    ch = i;
                    break;
                }
            }
            q.push(ch);
        }

        while (!q.empty()) {
            int v = q.front();
           // cout << " v = " << v<< endl;
            seq.pb(v);
            checked[v] = true;
            q.pop();

            for (int u : adj[v]) {
                deg[u]--;
                if (deg[u]==0 && !checked[u])
                    q.push(u);
            }
        }
    }

    eval(seq);
}

int main()
{
    FAST_IO;

    cin >> t >> n >> s;
    FOR(i, 1, n) {
        int k; cin >> k;
        REP(k) {
            int v; cin >> v;
            adj[v].pb(i);
            mustBef[i].pb(v);
            deg[i]++;
        }
    }

    topo1();

    REP(100)
        topo2();

    for (int x : ans) cout << x << "\n";

    return 0;
}

Subtask #1

47.7683604349 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	817 ms	52636 KB	Output is correct
2	Partially correct	493 ms	47372 KB	Output is partially correct
3	Partially correct	523 ms	47380 KB	Output is partially correct
4	Partially correct	552 ms	47404 KB	Output is partially correct
5	Partially correct	550 ms	47372 KB	Output is partially correct
6	Partially correct	531 ms	47428 KB	Output is partially correct
7	Partially correct	589 ms	48172 KB	Output is partially correct
8	Partially correct	837 ms	52740 KB	Output is partially correct
9	Partially correct	548 ms	47832 KB	Output is partially correct
10	Partially correct	533 ms	47384 KB	Output is partially correct