답안 #375384

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

//mt19937 rnd(time(NULL));

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++) {
        random_shuffle(adj[i].begin(), adj[i].end());
    }
    random_shuffle(order.begin(), order.end());

    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);
    srand(time(NULL));
    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 953 ms 3092 KB Output is correct
2 Partially correct 901 ms 484 KB Output is partially correct
3 Partially correct 901 ms 492 KB Output is partially correct
4 Partially correct 901 ms 500 KB Output is partially correct
5 Partially correct 902 ms 492 KB Output is partially correct
6 Partially correct 903 ms 620 KB Output is partially correct
7 Partially correct 908 ms 896 KB Output is partially correct
8 Partially correct 951 ms 2908 KB Output is partially correct
9 Partially correct 908 ms 696 KB Output is partially correct
10 Correct 901 ms 472 KB Output is correct