Submission #374699

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
374699	2021-03-07T21:43:08 Z	gustason	Fire drill (LMIO18_sauga)	C++11	31.1476 / 100	271 ms	24044 KB

sauga

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
set<int> adj[1005];
vector<char> col(1005, 0);
void dfs(int v) {
    col[v] = 1;

    auto it = adj[v].begin();
    while(it != adj[v].end()) {
        int u = *it;
        bool del = false;

        if (col[u] == 0) {
            dfs(u);
        } else if (col[u] == 1) {
            adj[v].erase(it++);
            del = true;
        }

        if (!del)
            ++it;
    }

    col[v] = 2;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t, n, S;
    cin >> t >> n >> S;

    for(int i = 0; i < n; i++) {
        int m;
        cin >> m;
        for(int j = 0; j < m; j++) {
            int x;
            cin >> x;
            adj[x].insert(i+1);
        }
    }

    for(int i = 0; i <= n; i++) {
        if (col[i] == 0) {
            dfs(i);
        }
    }

    vector<int> ind(n+1, 0);
    for(int i = 1; i <= 3; i++) {
        if (adj[i].empty()) continue;
        for(auto j : adj[i]) {
            ind[j]++;
        }
    }

    queue<int> q;
    for(int i = 1; i <= n; i++) {
        if (ind[i] == 0) {
            q.push(i);
        }
    }

    vector<int> ans;
    vector<bool> vis(n+1, false);

    while(!q.empty()) {
        int v = q.front();
        vis[v] = true;
        ans.push_back(v);
        q.pop();

        for(auto u : adj[v]) {
            ind[u]--;
            if (ind[u] == 0) {
                q.push(u);
                vis[u] = true;
            }
        }
    }

    for(int i : ans) {
        cout << i << "\n";
    }
    return 0;
}

Subtask #1

31.1475937763 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	119 ms	23916 KB	Output is partially correct
2	Partially correct	1 ms	492 KB	Output is partially correct
3	Partially correct	1 ms	620 KB	Output is partially correct
4	Partially correct	2 ms	768 KB	Output is partially correct
5	Partially correct	1 ms	620 KB	Output is partially correct
6	Partially correct	2 ms	640 KB	Output is partially correct
7	Partially correct	23 ms	3940 KB	Output is partially correct
8	Partially correct	271 ms	24044 KB	Output is partially correct
9	Partially correct	14 ms	2796 KB	Output is partially correct
10	Partially correct	1 ms	512 KB	Output is partially correct