Submission #374695

#	Time	Username	Problem	Language	Result	Execution time	Memory
374695		gustason	Fire drill (LMIO18_sauga)	C++11	31.37 / 100	187 ms	5984 KiB

sauga

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    srand(time(0));
    int t, n, S;
    cin >> t >> n >> S;

    vector<int> cant[n+1], in[n+1];
    for(int i = 0; i < n; i++) {
        int m;
        cin >> m;
        for(int j = 0; j < m; j++) {
            int x;
            cin >> x;
            cant[i].push_back(x);
            in[x].push_back(i);
        }
    }

    set<pair<int, int>> s;
    vector<int> cnt(n+1);
    for(int i = 0; i < n; i++) {
        s.insert({cant[i].size(), i});
        cnt[i] = cant[i].size();
    }

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

    for(int i = 0; i < n; i++) {
        auto it = s.begin();
        while(1) {
            it = s.begin();
            if (done[(*it).second]) {
                s.erase(it);
                continue;
            }
            break;
        }
        done[(*it).second] = true;
        ans.push_back((*it).second);
        s.erase(it);
        for(int j : in[(*it).second]) {
            s.erase({cnt[j], j});
            cnt[j]--;
            s.insert({cnt[j], j});
        }
    }

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

• Subtask 1: 31.365264187679998 / 100