はやし屋

競技プログラミングのメモ きたない

AOJ 2011: Gather the Maps!

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011

めっちゃ時間かけた...
long long やらんとダメです
ビットでやると楽

#include<iostream>
using namespace std;

int main(){
  int n ;
  while(cin >> n && n){
    bool isok[33][55] = {};
    // day , hito
    long long dp[33][55] = {};
    for(int i = 0 ; i < n ; ++i){
      dp[0][i] = 1ll << i;
    }
    for(int i = 0 ; i < n ; ++i){
      int  q; cin >> q;
      for(int j = 0 ; j < q ; ++j){
	int a ; cin >> a ;
	isok[a][i] = true;
      }
    }

    for(int i = 0 ; i < 30 ; ++i){
      long long u = 0ll;
      for(int j = 0 ; j < n ; ++j){
       	dp[i+1][j] = dp[i][j];
	if(isok[i+1][j])u|=dp[i][j];
      }
      for(int j = 0 ; j < n ; ++j)
	if(isok[i+1][j])dp[i+1][j] = u;
    }

    int ret = -1;

    for(int i = 1 ; i <= 30 ; ++i){
      for(int j = 0 ; j < n ; ++j){
	if(dp[i][j] == (1ll << n ) -1 )ret = i;
      }
      if(~ret)break;
    }
    cout << ret << endl;
  }

}