제출 #1289722

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

norela

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,m;
vector<int> a(3005,0);
int mn=LLONG_MAX;
vector<int> ans,cur;

void find(int x,int p) {
	if(x==m) {
		if(p==pow(2,n)-1&&(int)cur.size()<=mn) {
			mn=cur.size();
			ans=cur;
		}
		return;
	}
	find(x+1,p);
	cur.push_back(x);
	find(x+1,p^a[x]);
	cur.pop_back();
}

signed main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin>>n>>m;
	a.resize(m);
	for(int i=0; i<m; i++) {
		int x; cin>>x;
		for(int j=0; j<x; j++) {
			int g; cin>>g;
			a[i]|=(int)pow(2,g-1);
		}
	}
	find(0,0);
	cout<<mn<<"\n";
	for(int x:ans) cout<<x+1<<" ";
	
	return 0;
}

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