Seletiva IOI 2017

equipe.cpp

// Ivan Carvalho
// Equipe - Seletiva IOI - OBI 2017
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 201;
const int MAXM = 1024;
int mascara[MAXN],antimascara[MAXN],N,K;
int dp[MAXM][MAXM];
int main(){
	cin >> N >> K;
	int alvo = (1 << K) - 1;
	for(int i = 1;i<=N;i++){
		int qtd;
		cin >> qtd;
		antimascara[i] = (1 << K) - 1;
		while(qtd--){
			int x;
			cin >> x;
			x--;
			mascara[i] |= (1 << x);
		}
		antimascara[i] ^= mascara[i];
	}
	for(int i = 0;i<=alvo;i++) for(int j = 0;j<=alvo;j++) dp[i][j] = 2*MAXN;
	dp[0][0] = 0; 
	for(int i = 1;i<=N;i++){
		for(int mask1 = 0;mask1 <= alvo;mask1++){
			for(int mask2 = 0;mask2 <= alvo;mask2++){
				int b1 = mask1 | mascara[i];
				int b2 = mask2 | antimascara[i];
				dp[b1][b2] = min(dp[b1][b2], dp[mask1][mask2] + 1 );
			}
		}
	}
	if(dp[alvo][alvo] > N) cout << -1 << endl;
	else cout << dp[alvo][alvo] << endl;
	return 0;
}