답안 #375389

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375389 2021-03-09T10:24:36 Z gustason Fire drill (LMIO18_sauga) C++14
63.4993 / 100
947 ms 3336 KB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937 rnd(20210309);

const int maxN = 1005;
int best = 0;
vector<int> ans, seq, order;
int t, n, S;
vector<int> adj[maxN];
vector<char> col;
vector<bool> ok;
void dfs(int v) {
    if (!ok[v]) return;

    col[v] = '1';
    for(int u : adj[v]) {
        if (!ok[u]) continue;
//        cout << v << "-> " << u << " " << col[u] << "\n";
        if (col[u] == '0') {
            dfs(u);
        } else if (col[u] == '1') {
            ok[v] = false;
            return;
        }
    }
    col[v] = '2';
    seq.push_back(v);
}
void solve() {
    for(int i = 0; i <= n; i++) {
        shuffle(adj[i].begin(), adj[i].end(), rnd);
    }
    shuffle(order.begin(), order.end(), rnd);

    vector<int>().swap(seq);
    for(int i = 0; i <= n; i++) {
        col[i] = '0';
        ok[i] = true;
    }

    for(int i : order) {
//        cout << i << " ";
        if (col[i] == '0')
            dfs(i);
    }
//    cerr << "\n";

    vector<int> curr;
    for(int i = 1; i <= n; i++) {
        if (!ok[i])
            curr.push_back(i);
    }
//    for(int i : curr) {
//        cout << i << " ";
//    } cout << "\n";
    int good = n - (int) curr.size();
    if (good <= best) return;

    for(int i : seq) {
        curr.push_back(i);
    }

//    cout << good << "\n";
    ans = curr;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t >> n >> S;
    order.resize(n);
    col.resize(n+1);
    ok.resize(n+1);
    iota(order.begin(), order.end(), 1);
    for(int i = 0; i < n; i++) {
        int m;
        cin >> m;
        for(int j = 0; j < m; j++) {
            int x;
            cin >> x;
            adj[i+1].push_back(x);
        }
    }

    clock_t beg = clock();
    while((double) (clock() - beg) / CLOCKS_PER_SEC < 0.9) {
        solve();
    }
    for(int i : ans) {
        cout << i << "\n";
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 947 ms 3336 KB Output is correct
2 Partially correct 901 ms 616 KB Output is partially correct
3 Partially correct 901 ms 492 KB Output is partially correct
4 Partially correct 902 ms 632 KB Output is partially correct
5 Partially correct 901 ms 620 KB Output is partially correct
6 Partially correct 902 ms 620 KB Output is partially correct
7 Partially correct 907 ms 1004 KB Output is partially correct
8 Partially correct 946 ms 2924 KB Output is partially correct
9 Partially correct 906 ms 748 KB Output is partially correct
10 Correct 901 ms 476 KB Output is correct