Submission #1289828

#TimeUsernameProblemLanguageResultExecution timeMemory
1289828mefe123Norela (info1cup18_norela)C++20
100 / 100
519 ms580 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
	//	#pragma GCC optimize("0fast")
		using namespace std;
		vector<int> acevap;
		int cevaps=1e9;	
		
		void dene(int id,int sb,vector<int> &b,int m,int n,int sayac,vector<int> cevap){

			if(id==m){
				int kontrol=1;
					if(sb!=(1LL<<n)-1){
						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(acevap<cevap){
							kontrol=0;
							break;
							
						}
					}
					if(kontrol==1){
						cevaps=cevap.size();
						acevap=cevap;
					}
				}
				return;
			}
			

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

				}
			}
			int sb=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...