oj.uz

Submission #223792

# Submission time Handle Problem Language Result Execution time Memory
223792 2020-04-16T13:11:14 Z johutha Political Development (BOI17_politicaldevelopment) C++14
0 / 100
 3000 ms 5368 KB 
#include <iostream>
#include <vector>
#include <set>
#include <bitset>
#include <cassert>

#define int int64_t
#define bs bitset<10>

using namespace std;

struct findcliq
{
    int n;
    vector<bool> b;
    vector<vector<bool>> adjmat;

    int find()
    {
        assert(n <= 10);
        b.resize(1<<n);
        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;
            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";
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Execution timed out 3083 ms 5368 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Execution timed out 3083 ms 5368 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3086 ms 4588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Execution timed out 3083 ms 5368 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Execution timed out 3083 ms 5368 KB Time limit exceeded
4 Halted 0 ms 0 KB -