Submission #451276

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
451276	2021-08-03T07:03:45 Z	Aldas25	Fire drill (LMIO18_sauga)	C++14	46.3605 / 100	93 ms	54600 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];

void topo () {
    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);
}

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]++;
        }
    }

    topo();

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

    return 0;
}

Subtask #1

46.3604624004 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	54596 KB	Output is correct
2	Partially correct	31 ms	47280 KB	Output is partially correct
3	Partially correct	33 ms	47388 KB	Output is partially correct
4	Partially correct	35 ms	47428 KB	Output is partially correct
5	Partially correct	35 ms	47300 KB	Output is partially correct
6	Partially correct	34 ms	47456 KB	Output is partially correct
7	Partially correct	41 ms	48460 KB	Output is partially correct
8	Partially correct	93 ms	54600 KB	Output is partially correct
9	Partially correct	35 ms	47976 KB	Output is partially correct
10	Partially correct	31 ms	47288 KB	Output is partially correct