LEM2 - GUMBI

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<queue>
using namespace std;

int n, k, a[30], start;
bool check[1<<20];

void enter() {
	scanf("%d%d",&n,&k); k = 1 << (k-1); 
	for(int i = 0; i < n; ++i) {
		int s; scanf("%d", &s);
		a[i] = -1;
		for(int j = 0; j < s; ++j) {
			int t; scanf("%d",&t);
			a[i] &= ~(1 << (t-1));
		}
	}
	start = 0;
	for(int i = 0; i < n; ++i) {
		int t; scanf("%d",&t);
		if(t) start |= 1 << i;
	}
}

void solve() {
	queue<int> qu; qu.push(start); check[start] = 1;
	for(int step = 0; !qu.empty(); ++step) 
	for(int Z = qu.size()-1; Z >= 0; --Z) {
		int state = qu.front(); qu.pop();
		if(state == k) {
			printf("%d\n", step); return;
		}
		for(int i = 0; i < n; ++i) {
			int newState = (state & a[i]) | (1 << i);
			if(!check[newState]) {
				check[newState] = 1;
				qu.push(newState);
			}
		}
	}
	printf("-1\n");
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	enter();
	solve();
}

Download