Submission #400145

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
400145	2021-05-07T13:08:58 Z	johutha	Political Development (BOI17_politicaldevelopment)	C++14	Compilation error	0 ms	0 KB

politicaldevelopment

#include <iostream>
#include <vector>
#include <unordered_set>
#include <bitset>
#include <cassert>

#define bs bitset<10>
 
using namespace std;
 
struct findcliq
{
    int n;
    bitset<10> b;
    vector<bitset<10>> 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<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";
}

Compilation message

politicaldevelopment.cpp: In member function 'int findcliq::find()':
politicaldevelopment.cpp:20:11: error: 'class std::bitset<10>' has no member named 'resize'; did you mean 'size'?
   20 |         b.resize(1<<n);
      |           ^~~~~~
      |           size
politicaldevelopment.cpp: At global scope:
politicaldevelopment.cpp:65:5: error: 'multiset' does not name a type
   65 |     multiset<pair<int,int>> act;
      |     ^~~~~~~~
politicaldevelopment.cpp: In member function 'int graph::solve()':
politicaldevelopment.cpp:72:13: error: 'act' was not declared in this scope
   72 |             act.insert({adjset[i].size(), i});
      |             ^~~
politicaldevelopment.cpp:75:17: error: 'act' was not declared in this scope
   75 |         while (!act.empty())
      |                 ^~~
politicaldevelopment.cpp:84:48: error: no matching function for call to 'std::vector<std::bitset<10> >::resize(int&, std::vector<bool>)'
   84 |             fq.adjmat.resize(n, vector<bool>(n));
      |                                                ^
In file included from /usr/include/c++/9/vector:67,
                 from politicaldevelopment.cpp:2:
/usr/include/c++/9/bits/stl_vector.h:934:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = std::bitset<10>; _Alloc = std::allocator<std::bitset<10> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
  934 |       resize(size_type __new_size)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:934:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/9/bits/stl_vector.h:954:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = std::bitset<10>; _Alloc = std::allocator<std::bitset<10> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::bitset<10>]'
  954 |       resize(size_type __new_size, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:954:54: note:   no known conversion for argument 2 from 'std::vector<bool>' to 'const value_type&' {aka 'const std::bitset<10>&'}
  954 |       resize(size_type __new_size, const value_type& __x)
      |                                    ~~~~~~~~~~~~~~~~~~^~~