Submission #45501

#	Time	Username	Problem	Language	Result	Execution time	Memory
45501		IvanC	Norela (info1cup18_norela)	C++17	100 / 100	94 ms	564 KiB

norela

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll menor,N,M,mascaras[30],alvo,menormask;
void brute(int atual,ll bitmask,int qtd,ll outramask){
	if(atual == M){
		if(bitmask != alvo) return;
		if(qtd < menor){
			menor = qtd;
			menormask = outramask;
		}
		else if(qtd == menor){
			for(ll i = 0;i<M;i++){
				if((outramask & (1LL << i)) && !(menormask & (1LL << i)) ){
					menormask = outramask;
					break;
				}
			}
		}
		return;
	}
	brute(atual+1, bitmask,qtd, outramask );
	brute(atual+1, bitmask ^ mascaras[atual], qtd+1, outramask | (1LL << atual) );
}
int main(){
	cin >> N >> M;
	menor = 2*M;
	alvo = (1LL << N) - 1;
	for(ll i = 0;i<M;i++){
		ll x;
		cin >> x;
		while(x--){
			ll y;
			cin >> y;
			y--;
			mascaras[i] |= (1LL << y);
		}
	}
	brute(0,0,0,0);
	cout << menor << endl;
	for(ll i = 0;i<M;i++){
		if(menormask & (1LL << i)){
			cout << i + 1 << " ";
		}
	}
	cout << endl;
	return 0;
}

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