Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- set<int> inters(set<int> &a, set<int> &b) {
- set<int> c;
- set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.end()));
- return c;
- }
- set<int> compsub;
- int ans = 0;
- void extend(set<int> candidates, set<int> nott, vector<vector<bool> > &a, vector<int> &c, vector<set<int>> &b) {
- cout << "c " << candidates.size() << endl;
- for (int v : compsub) {
- cout << v << " ";
- }
- cout << endl;
- cout << "cand " << nott.size() << endl;
- for (int v : candidates) {
- cout << v << " ";
- }
- cout << endl << endl;
- if (candidates.empty() && nott.empty()) {
- int ans1 = 0;
- for (int k : compsub) {
- ans1 += b[k].size();
- }
- cout << "ans " << ans1 << endl;
- ans = max(ans1, ans);
- return;
- }
- while (candidates.size() > 0) {
- set<int> nv;
- // cout << "ca " << v << endl;
- int v = *candidates.begin();
- for (int i = 0; i < a.size(); ++i)
- if (!a[v][i])
- {
- nv.insert(i);
- }
- // cout << nv.size() << endl;
- compsub.insert(v);
- extend(inters(nv, candidates), inters(nv, nott), a, c, b);
- compsub.erase(v);
- candidates.erase(v);
- nott.insert(v);
- }
- }
- int main() {
- int t, m, n, temp;
- cin >> t;
- for (int k = 0; k < t; ++k) {
- cin >> m;
- cin >> n;
- vector<vector<bool> > a(m, vector<bool> (m, true));
- vector<set<int> > b(m);
- vector<int> c(m);
- for (int i = 0; i < m; ++i) {
- cin >> c[i];
- for (int j = 0; j < c[i]; ++j) {
- cin >> temp;
- temp--;
- b[i].insert(temp);
- }
- }
- for (int i = 0; i < m; ++i) {
- for (int j = i + 1; j < m; ++j) {
- if (inters(b[i], b[j]).size() == 0) {
- a[i][j] = a[j][i] = false;
- }
- }
- }
- /*for (int i = 0; i < m; ++i) {
- for (int j = 0; j < m; ++j) {
- cout << a[i][j] << " ";
- }
- cout << endl;
- }*/
- set<int> candidates;
- set<int> nott;
- for (int i = 0; i < m; ++i) {
- candidates.insert(i);
- }
- extend(candidates, nott, a, c, b);
- cout << "ATTENTION" << ans;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement