| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 400149 | 2021-05-07T13:11:15 Z | johutha | Political Development (BOI17_politicaldevelopment) | C++14 | 0 ms | 0 KB |
#include <iostream>
#include <vector>
#include <unordered_set>
#include <bitset>
#include <cassert>
#include <set>
#define bs bitset<10>
using namespace std;
struct findcliq
{
int n;
bitset<1024> b;
vector<bitset<1024>> 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<unordered_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;
fq.adjmat.resize(n, vector<bool>(n));
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";
}