제출 #1289649

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289649		azradudukalay	Norela (info1cup18_norela)	C++20	50 / 100	878 ms	576 KiB

norela

#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";
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25