UOA1032: Course Planning for Lazy Students

ACM-ICPC Japan Domestic Warm Up IのD問題。BFSで解けるという噂を聞いたのでやってみました。
ノーデバッグで一発Accepted。なんと。
実行時間がすごいことになりました。高速化したくなった問題はいくらでもありますが、むしろ高速化したくない問題は初めてです。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>

#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

#define REP(i,e) for(int i=0;i<(int)(e);i++)
#define FOR(i,b,e) for(int i=(b);i<(int)(e);i++)
#define ALL(c) (c).begin(), (c).end()
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)

const int N=20;

int req[N];
int deg[N];
bool done[1<<N];

struct state{ int s,c; };

int bitcount(int n){ return n ? (n&1)+bitcount(n>>1) : 0; }

int BFS(int n,int r){
  queue<state> qu;
  for(qu.push((state){0,0});qu.size();qu.pop()){
    state s=qu.front();
    if(done[s.s]) continue;
    done[s.s]=true;

    if(s.c>=r) return bitcount(s.s);
    REP(i,n) if(!(s.s&(1<<i)) && (req[i]&s.s)==req[i])
      qu.push((state){s.s|(1<<i),s.c+deg[i]});
  }

  assert(false);
}

main(){
  int n,r;
  while(cin >> n >> r && n|r){
    REP(i,n){
      int a,b;
      req[i]=0;
      cin >> deg[i] >> a;
      REP(j,a) cin >> b, req[i]=req[i]|(1<<b);
    }

    REP(i,1<<n) done[i]=false;
    cout << BFS(n,r) << endl;
  }
}