Codeforces Round #533 (Div. 2) E - Helping Hiasat 最大团

E - Helping Hiasat

裸的最大团，写了一种 2 ^ (m / 2)  * (m / 2)的复杂度的壮压， 应该还有更好的方法。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 2e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

const double eps = 1e-;

int n, m, op;

LL e[];

int a[<<], b[<<];

string name;

set<int> Set;

map<string, int> Map;

int main() {

    cin >> n >> m;

    for(int i = ; i <= n; i++) {

        cin >> op;

        if(op == ) {

            Set.clear();

        } else {

            cin >> name;

            if(Map.find(name) == Map.end())

                Map[name] = SZ(Map);

            int x = Map[name];

            for(auto& y : Set) {

                e[x - ] |= 1ll << (y - );

                e[y - ] |= 1ll << (x - );

            }

            Set.insert(x);

        }

    }

    int c1 = m / , c2 = m - c1;

    for(int S = ; S < ( << c1); S++) {

        int p = __builtin_ctz(S), tmp = ;

        a[S] = max(a[S], a[S ^ ( << p)]);

        for(int i = ; i < c1; i++)

            if(!(e[p]>>i&)) tmp |=  << i;

        a[S] = max(a[S], a[tmp & (S ^ ( << p))] + );

    }

    for(int S = ; S < ( << c2); S++) {

        int p = __builtin_ctz(S), tmp = ;

        b[S] = max(b[S], b[S ^ ( << p)]);

        for(int i = ; i < c2; i++)

            if(!(e[p + c1]>>(i+c1)&)) tmp |=  << i;

        b[S] = max(b[S], b[tmp & (S ^ ( << p))] + );

    }

    int ans = ;

    for(int S = ; S < ( << c2); S++) {

        LL tmp = ;

        for(int i = ; i < c2; i++)

            if(S >> i & ) tmp |= e[i + c1];

        for(int i = ; i < c1; i++) tmp ^=  << i;

        tmp &= ( << c1) - ;

        ans = max(ans, b[S] + a[tmp]);

    }

    printf("%d\n", ans);

    return ;

}

/*

*/