Submission #1289914

#TimeUsernameProblemLanguageResultExecution timeMemory
1289914amodiNorela (info1cup18_norela)C++20
50 / 100
1096 ms580 KiB
//#pragma GCC target("tune=native")
//#pragma GCC optimize("03,inline,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long 

 vector<vector<bool>>a;
 int n;
 int m;
 vector<int>mn;
 int mnsz=1e9+5;
 void f(vector<int>suan,int i,vector<bool>b) {
	
	 
	 bool flag=1;
	 for(int i=0;i<n;i++) {
		 if(!b[i]){
			 flag=0;
			 break;
		 }
	 }
	 if(flag){
		 
			 if(suan.size()<mnsz){
				 mnsz=suan.size();
				 mn=suan;
				 return;
			 }
			 else if(suan.size()==mnsz){
				 for(int i=0;i<mnsz;i++) {
					 if(suan[i]<mn[i]) {
						 mn=suan;
						 return;
					 }
				 }
			 }
				 
			 
		 
	 	
 }if(i+1>m)return;
 f(suan,i+1,b);
  
     for(int j=0;j<n;j++) {
		 b[j]=b[j]^a[i][j];
	 }
	 suan.push_back(i+1);
	 if(suan.size()<=mnsz)f(suan,i+1,b);
	 
	 }
 
int32_t main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   cin>>n>>m;
   vector<bool>bas(n,0);
   vector<int>bombos;
   a.resize(m,vector<bool>(n));
   for(int i=0;i<m;i++) {
	   int k;
	   cin>>k;
	   a[i].resize(k);
	   for(int j=0;j<k;j++) {
		   int x;
		   cin>>x;
		   x--;
		  a[i][x]=1;
	   }
   }
   f(bombos,0,bas);
   cout<<mnsz<<endl;
   for(int i=0;i<mnsz;i++){
	   cout<<mn[i]<<" ";
   }
   return 0;
  }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...