SHARE
TWEET

Untitled

DiegoDF1445 May 25th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. #define all(a) a.begin(), a.end()
  5. #define forn(l, r) for(int i = l; i < (r); ++i)
  6. #define F first
  7. #define S second
  8. #define $ ios::sync_with_stdio(0);
  9. ///#define int long long int
  10.  
  11. using namespace std;
  12. using namespace __gnu_pbds;
  13. using ll = long long int;
  14. using ii = pair<int, int>;
  15. using li = pair<ll, int>;
  16. using vi = vector<int>;
  17. using graph = vector<vi>;
  18. using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
  19.  
  20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  21.  
  22. const ll mod =  1000000007;
  23. const int INF = 0x3f3f3f3f;
  24. const int MAXN = 323;
  25. const double pi = 3.14159265359;
  26. const double eps = 0.00000001;
  27. ll cost[MAXN];
  28. //int dp[21][1<<21];
  29. int  n, m;
  30. bool testmask(int mask) {
  31.     ll nova = 0;
  32.     for (int i = 0; 1<<i <= mask; ++i) {
  33.         if (mask&1<<i) {
  34.             nova |= cost[i];
  35.         }
  36.     }
  37.     return 1ll << m == mask +1;
  38. }
  39. int sol(int i, int mask) {
  40.     if (testmask(mask)) {
  41.         return 0;
  42.     }
  43.     if (i == n) return n;
  44.  
  45.     int ans = sol(i+1, mask);
  46.     ans = min(1+sol(i+1, mask|1<<i), ans);
  47.     return ans;
  48. }
  49.  
  50. int32_t main() {
  51.  
  52.     //freopen("input.txt", "r+", stdin);
  53.     //freopen("output.txt", "w+", stdout);
  54.     scanf("%d %d", &n ,&m );
  55.     for (int i = 0, k, a; i<n; ++i) {
  56.         scanf("%d", &k);
  57.         while (k--) {
  58.             scanf("%d", &a);
  59.             a--;
  60.             cost[i]|=1LL<<a;
  61.         }
  62.     }
  63.  
  64.     printf("%d\n", sol(0, 0));  
  65. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top