Submission #223834

#TimeUsernameProblemLanguageResultExecution timeMemory
223834jk_Political Development (BOI17_politicaldevelopment)C++14
100 / 100
548 ms29688 KiB
#include <iostream>
#include <vector>
#include <set>
#include <bitset>
#include <cassert>
#include <array>

#define int int64_t
#define bs bitset<10>

using namespace std;


struct findcliq
{
  int n;
  bitset<(1<<10)> b;
  array<bitset<10>, 10> adjmat;

  int find()
  {
    assert(n <= 10);
    b[0] = 1;
    int mmax = 0;

    for (int i = 1; i < (1<<n); i++)
      {
	for (int ad = 0; ad < n; ad++)
	  {
	    if (!(i & (1<<ad))) continue;
	    int ls = i - (1<<ad);
	    if (!b[ls]) continue;
	    bool ok = true;
	    for (int in = 0; in < n; in++)
	      {
		if ((1<<in) & ls)
		  {
		    if (!adjmat[in][ad]) ok = false;
		  }
	      }
	    b[i] = b[i] | ok;
	  }
	if (b[i]) mmax = max(mmax, (int)__builtin_popcount(i));
      }
    return mmax;
  }

  void print()
  {
    cout << n << "\n";
    for (int i = 0; i < n; i++)
      {
	for (int j = 0; j < n; j++)
	  {
	    cout << adjmat[i][j];
	  }
	cout << "\n";
      }
    cout << "\n";
  }
};

struct graph
{
  int n;
  vector<set<int>> adjset;
  multiset<pair<int,int>> act;

  int solve()
  {
    int res = 0;
    for (int i = 0; i < n; i++)
      {
	act.insert({adjset[i].size(), i});
      }

    while (!act.empty())
      {
	int curr = act.begin()->second;
	act.erase(act.begin());

	int sz = adjset[curr].size() + 1;

	findcliq fq;
	fq.n = sz;
	
	vector<int> all(adjset[curr].begin(), adjset[curr].end());
	all.push_back(curr);

	for (int i = 0; i < sz; i++)
	  {
	    for (int j = 0; j < sz; j++)
	      {
		fq.adjmat[i][j] = adjset[all[i]].count(all[j]);
	      }
	  }

	for (auto next : adjset[curr])
	  {
	    act.erase({adjset[next].size(), next});
	    adjset[next].erase(curr);
	    act.insert({adjset[next].size(), next});
	  }
	res = max(res, fq.find());
      }
    return res;
  }
};

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
    
  int n, k;
  cin >> n >> k;

  graph g;
  g.n = n;
  g.adjset.resize(n);

  for (int i = 0; i < n; i++)
    {
      int cnt;
      cin >> cnt;
      for (int j = 0; j < cnt; j++)
        {
	  int a;
	  cin >> a;
	  g.adjset[i].insert(a);
        }
    }
  cout << g.solve() << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...