Submission #1289649

#TimeUsernameProblemLanguageResultExecution timeMemory
1289649azradudukalayNorela (info1cup18_norela)C++20
50 / 100
878 ms576 KiB
#include <bits/stdc++.h>
using namespace std;
int n, m, en_az;
vector<vector<int>> buyu;
vector<int> cozum;
void dfs(int idx, vector<bool> &kart, vector<int> &secilen) {
    if(idx == m) {
        bool hepsi_duz = true;
        for(bool b : kart) if(!b) hepsi_duz = false;
        if(hepsi_duz) {
            if(secilen.size() < en_az || (secilen.size() == en_az && secilen < cozum)) {
                en_az = secilen.size();
                cozum = secilen;
            }
        }
        return;
    }
    dfs(idx + 1, kart, secilen);
    for(int c : buyu[idx]) kart[c] = !kart[c];
    secilen.push_back(idx + 1);
    dfs(idx + 1, kart, secilen);
    secilen.pop_back();
    for(int c : buyu[idx]) kart[c] = !kart[c];
}
int main() {
    cin >> n >> m;
    buyu.resize(m);
    for(int i = 0; i < m; i++) {
        int k;
        cin >> k;
        buyu[i].resize(k);
        for(int j = 0; j < k; j++) {
            cin >> buyu[i][j];
            buyu[i][j]--;
        }
    }
    vector<bool> kart(n, false);
    en_az = m + 1;
    vector<int> secilen;
    dfs(0, kart, secilen);
    cout << en_az << "\n";
    for(int i = 0; i < cozum.size(); i++) {
        if(i) cout << " ";
        cout << cozum[i];
    }
    cout << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...