AOJ2011 Gather the Maps!

Gather the Maps! | Aizu Online Judge

Introduction to Programming Introduction to Algorithms and Data Structures Library of Data Structures Library of Graph Algorithms Library of Computational Geometry Library of Dynamic Programming Library of Number Theory

この追記の部分の通り， から順番に誰と会えるかを で管理して，初めて 人揃った時の日にちを出力した． なのでllに収まるのでビットで管理した．会う，というのが論理和で出来るので楽に感じた．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <bitset>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

bool used[55][35];

int main() {
  int n;
  while(cin >> n && n) {

      memset(used, 0, sizeof(used));
      rep(i, n) {
          int x;
          cin >> x;
          rep(j, x) {
              int y;
              cin >> y;

              used[i][y] = true;
          }
      }

      ll S[55];
      memset(S, 0, sizeof(S));

      bool flag = true;
      rep(i, 35) {
          rep(j, n) {
              rep(k, n) {
                  if(used[j][i] && used[k][i]) {
                      ll sum = (S[j] | S[k]);
                      sum |= (1LL << j);
                      sum |= (1LL << k);

                      S[j] = S[k] = sum;
                  }
              }
          }

          rep(j, n) {
              if(__builtin_popcountll(S[j]) == n) {
                  cout << i << endl;
                  flag = false;
                  break;
              }
          }

          if(!flag) break;
      }

      if(flag) cout << -1 << endl;
  }

  return 0;
}
Mar 22nd, 2016
300, aoj-icpc