oj.uz

Submission #374695

# Submission time Handle Problem Language Result Execution time Memory
374695 2021-03-07T21:08:12 Z gustason Fire drill (LMIO18_sauga) C++11
31.3653 / 100
 187 ms 5984 KB 
#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.3652641877 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 124 ms 5868 KB Output is partially correct
2 Partially correct 2 ms 512 KB Output is partially correct
3 Partially correct 2 ms 492 KB Output is partially correct
4 Partially correct 3 ms 512 KB Output is partially correct
5 Partially correct 2 ms 492 KB Output is partially correct
6 Partially correct 3 ms 492 KB Output is partially correct
7 Partially correct 23 ms 1388 KB Output is partially correct
8 Partially correct 187 ms 5984 KB Output is partially correct
9 Partially correct 16 ms 1004 KB Output is partially correct
10 Partially correct 1 ms 492 KB Output is partially correct