Submission #491435

#	Time	Username	Problem	Language	Result	Execution time	Memory
491435		Rainbowbunny	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	194 ms	29060 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
const int MAXB = 10;

int n, kk;
set <int> M[MAXN];
int minbit[1 << MAXB], f[MAXB], cnt[1 << MAXB];
bitset <1 << MAXB> B;
bool Vis[MAXN];

int Check(int i)
{
    int ans = 1;
    int sz = M[i].size();
    vector <int> Adj;
    for(auto x : M[i])
    {
        Adj.push_back(x);
    }
    for(int j = 0; j < sz; j++)
    {
        f[j] = 0;
    }
    for(int j = 0; j < sz; j++)
    {
        for(int k = j + 1; k < sz; k++)
        {
            if(M[Adj[j]].count(Adj[k]))
            {
                f[j] |= (1 << k);
                f[k] |= (1 << j);
            }
        }
        f[j] |= (1 << j);
    }
    B.reset();
    B[0] = 1;
    for(int j = 1; j < (1 << sz); j++)
    {
        if((f[minbit[j]] & j) == j and B[j ^ (1 << minbit[j])])
        {
            B[j] = true;
            ans = max(ans, cnt[j] + 1);
        }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(int i = 1; i < 1 << MAXB; i++)
    {
        for(int j = 0; j < MAXB; j++)
        {
            if(i & (1 << j))
            {
                minbit[i] = j;
                cnt[i] = cnt[i ^ (1 << j)] + 1;
                break; 
            }
        }
    }
    cin >> n >> kk;
    for(int i = 0; i < n; i++)
    {
        int sz;
        cin >> sz;
        for(int j = 0; j < sz; j++)
        {
            int a;
            cin >> a;
            M[i].emplace(a);
        }
    }
    int ans = 1;
    queue <int> Q;
    for(int i = 0; i < n; i++)
    {
        if((int)M[i].size() < kk)
        {
            Q.push(i);
            Vis[i] = true;
        }
    }
    while(Q.empty() == false)
    {
        int node = Q.front();
        ans = max(ans, Check(node));
        Q.pop();
        for(auto x : M[node])
        {
            M[x].erase(node);
            if((int)M[x].size() < kk and !Vis[x])
            {
                Q.push(x);
                Vis[x] = true;
            }
        }
        M[node].clear();
    }
    cout << ans << '\n';
}

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