제출 #1289625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289625		gecepanteri	Norela (info1cup18_norela)	C++20	50 / 100	1096 ms	580 KiB

norela

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;

int n = 0;
int m = 0;
int min_size = INT_MAX;
vector <vector<int>> buyuler;
set <vector<int>> st;

inline void dp(int ind, vector <bool> dizi, vector <int> used_buyuler){
    bool flag = true;
    for(bool temp : dizi){
        if(temp == false){
            flag = false;
            break;
        }
    }
    if(flag == true){
        st.insert(used_buyuler);
        min_size = min(min_size, (int)used_buyuler.size());
        return ;
    }
    if(ind >= m){
        return ;
    }
    dp(ind + 1, dizi, used_buyuler);
    for(int tmp : buyuler[ind]){
        dizi[tmp - 1] = !dizi[tmp - 1];
    }
    if(used_buyuler.size() + 1 > min_size){
        return ;
    }
    used_buyuler.push_back(ind);
    dp(ind + 1, dizi, used_buyuler);
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin >> n >> m;
    buyuler.resize(m);
    for(int i = 0; i < m; i++){
        int k = 0;
        cin >> k;
        for(int j = 0; j < k; j++){
            int tmp = 0;
            cin >> tmp;
            buyuler[i].push_back(tmp);
        }
    }
    vector <bool> dizim;
    dizim.assign(n, false);
    vector <int> tempv;
    dp(0, dizim, tempv);
    vector <int> cevap;
    for(auto wasd : st){
        if(wasd.size() <= min_size){
            cevap = wasd;
            break;
        }
    }
    cout << cevap.size() << endl;
    for(int tmp : cevap){
        cout << tmp + 1 << " ";
    }
    cout << endl;
}

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