Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <algorithm>
- #include <vector>
- #include <string.h>
- using namespace std;
- #define MAX_N 25
- #define MAX_K 45
- int t; int k,n;
- int sk[MAX_K];
- int openk[MAX_N];
- vector<int> keyins[MAX_N];
- int dp[(1<<20)+10];
- int memp[(1<<20)+10];
- int doit(int bm) {
- if (dp[bm]!=-1)
- return dp[bm];
- dp[bm]=0;
- int keysAv[210];
- memset(keysAv,0,sizeof(keysAv));
- for (int i=0; i<k; i++)
- keysAv[sk[i]]++;
- for (int i=0; i<n; i++)
- if ((1<<i)&bm) {
- keysAv[openk[i]]--;
- for (int j=0; j<(int)keyins[i].size(); j++)
- keysAv[keyins[i][j]]++;
- }
- for (int i=0; i<n; i++) {
- if (keysAv[openk[i]]==0) continue;
- if (doit(bm|(1<<i))) {
- if (dp[bm]!=1) memp[bm]=i;
- dp[bm]=1;
- }
- }
- return dp[bm];
- }
- int main() {
- scanf("%d", &t);
- for (int casen=1; casen<=t; casen++) {
- scanf("%d %d", &k,&n);
- for (int i=0; i<n; i++)
- keyins[i].clear();
- for (int i=0; i<k; i++)
- scanf("%d", &sk[i]);
- for (int i=0; i<n; i++) {
- int tmp;
- scanf("%d %d", &openk[i], &tmp);
- for (int j=0; j<tmp; j++) {
- int ktmp;
- scanf("%d", &ktmp);
- keyins[i].push_back(ktmp);
- }
- }
- memset(dp,-1,sizeof(dp));
- memset(memp,-1,sizeof(memp));
- dp[(1<<n)-1]=1;
- printf("Case #%d:", casen);
- if (doit(0)!=1) {
- printf(" IMPOSSIBLE\n");
- continue;
- }
- int mask=0;
- while (memp[mask]!=-1) {
- printf(" %d", memp[mask]);
- mask|=(1<<memp[mask]);
- }
- printf("\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement