Advertisement
Guest User

Untitled

a guest
Feb 24th, 2020
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.43 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. set<int> inters(set<int> &a, set<int> &b) {
  6.     set<int> c;
  7.     set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.end()));
  8.     return c;
  9. }
  10.  
  11. set<int> compsub;
  12. int ans = 0;
  13.  
  14. void extend(set<int> candidates, set<int> nott, vector<vector<bool> > &a, vector<int> &c, vector<set<int>> &b) {
  15.     cout << "c " << candidates.size() << endl;
  16.     for (int v : compsub) {
  17.         cout << v << " ";
  18.     }
  19.     cout << endl;
  20.     cout << "cand " << nott.size() << endl;
  21.     for (int v : candidates) {
  22.         cout << v << " ";
  23.     }
  24.     cout << endl << endl;
  25.    
  26.     if (candidates.empty() && nott.empty()) {
  27.         int ans1 = 0;
  28.         for (int k : compsub) {
  29.             ans1 += b[k].size();
  30.         }
  31.         cout << "ans " << ans1 << endl;
  32.         ans = max(ans1, ans);
  33.         return;
  34.     }
  35.     while (candidates.size() > 0) {
  36.         set<int> nv;
  37.       //  cout << "ca " << v << endl;
  38.         int v = *candidates.begin();
  39.         for (int i = 0; i < a.size(); ++i)
  40.         if (!a[v][i])
  41.         {
  42.             nv.insert(i);
  43.         }
  44.      //   cout << nv.size() << endl;
  45.         compsub.insert(v);
  46.         extend(inters(nv, candidates), inters(nv, nott), a, c, b);
  47.         compsub.erase(v);
  48.         candidates.erase(v);
  49.         nott.insert(v);
  50.     }
  51. }
  52.  
  53. int main() {
  54.     int t, m, n, temp;
  55.     cin >> t;
  56.     for (int k = 0; k < t; ++k) {
  57.         cin >> m;
  58.         cin >> n;
  59.         vector<vector<bool> > a(m, vector<bool> (m, true));
  60.         vector<set<int> > b(m);
  61.         vector<int> c(m);
  62.         for (int i = 0; i < m; ++i) {
  63.             cin >> c[i];
  64.             for (int j = 0; j < c[i]; ++j) {
  65.                 cin >> temp;
  66.                 temp--;
  67.                 b[i].insert(temp);
  68.             }
  69.         }
  70.         for (int i = 0; i < m; ++i) {
  71.             for (int j = i + 1; j < m; ++j) {
  72.                 if (inters(b[i], b[j]).size() == 0) {
  73.                     a[i][j] = a[j][i] = false;
  74.                 }
  75.             }
  76.         }
  77.         /*for (int i = 0; i < m; ++i) {
  78.             for (int j = 0; j < m; ++j) {
  79.                 cout << a[i][j] << " ";
  80.             }
  81.             cout << endl;
  82.         }*/
  83.         set<int> candidates;
  84.         set<int> nott;
  85.         for (int i = 0; i < m; ++i) {
  86.             candidates.insert(i);
  87.         }
  88.         extend(candidates, nott, a, c, b);
  89.         cout << "ATTENTION" << ans;
  90.     }
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement