Submission #400150

#	Time	Username	Problem	Language	Result	Execution time	Memory
400150		johutha	Political Development (BOI17_politicaldevelopment)	C++14	54 / 100	3090 ms	33168 KiB

politicaldevelopment

#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, bitset<1024>());
 
            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";
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 0 / 23
• Subtask 4: 38 / 38
• Subtask 5: 0 / 23