제출 #1289672

#제출 시각아이디문제언어결과실행 시간메모리
1289672mefe123Norela (info1cup18_norela)C++20
0 / 100
39 ms576 KiB
	#include <iostream> 
	#include <vector> 
	#include <string> 
	#include <algorithm>
	#include <cmath> 
	#include <map>
	#include <set>
	#include <queue>	
	#include <stack>
	#include <unordered_map>
	#include <unordered_set>
	#include <bitset>
	#include <numeric>
	#include <functional>
	#include <iomanip>
	#include <sstream>

	#define int long long

	using namespace std;
	vector<int> acevap;
	int cevaps=1e9;
	void dene(int id,vector<int> sb,vector<vector<int>> &b,int m,int n,int sayac,vector<int> cevap){
		if(id==m){
			int kontrol=1;
			for(auto go:sb){
				if(go==0){
					kontrol=0;
				}
			}
			if(kontrol==1&&cevap.size()<cevaps){
				cevaps=cevap.size();
				acevap=cevap;
			}
			else if(cevap.size()==cevaps){
				for(int i=0;i<cevap.size();i++){
					if(cevap[i]>acevap[i]){
						kontrol=0;
						break;
						
					}
				}
				if(kontrol==1){
					cevaps=cevap.size();
					acevap=cevap;
				}
			}
			return;
		}
		

		dene(id+1,sb,b,m,n,sayac,cevap);
		vector<int> ysb1=sb;
		for(int i=0;i<n;i++){
			ysb1[i]=ysb1[i]^b[id][i];
		}
		cevap.push_back(id);
		dene(id+1,ysb1,b,m,n,sayac+1,cevap);
	}
	
	void solve(int n,int m){
		vector<vector<int>> b(m,vector<int>(n,0));
		for(int i=0;i<m;i++){
			int x;
			cin>>x;
			for(int j=0;j<x;j++){
				int v;
				cin>>v;
				b[i][v-1]=1;
			}
		}
		vector<int> sb(n,0);
		vector<int> cevap;
		dene(0,sb,b,m,n,0,cevap);
		if(acevap.size()==0){
			cout<<-1<<endl;
		}
		else{
			cout<<acevap.size()<<endl;
			for(int i=0;i<acevap.size();i++){
				cout<<acevap[i]+1<<" ";
			}
		}
	}

	signed main(){
		int t=1;
		//cin>>t;
		while(t--){
			int n,m;
			cin>>n>>m;
			solve(n,m);
		}
	}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...