Submission #480716

#	Time	Username	Problem	Language	Result	Execution time	Memory
480716		hidden1	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	504 ms	31228 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#ifndef LOCAL
#define cerr if(false) cerr
#endif

#define forn(N)    for(int i =   0; i < (N); i ++)
#define forab(A, B) for(int i = (A); i < (B); i ++)

const int MAX_N = 1e5 + 10;
set<int> g[MAX_N];
int n, k;

const int MAX_K = 10;
bool adj[MAX_K][1 << MAX_K], can[1 << MAX_K];
int pw[MAX_N];

int solve() {
    multiset<pair<int, int> > st;
    forn(n) {
        st.insert({g[i].size(), i});
    }

    auto rmEdge = [&st](int a, int b) {
        st.erase({g[a].size(), a});
        st.erase({g[b].size(), b});
        g[a].erase(b);
        g[b].erase(a);
        if(g[a].size() != 0) {
            st.insert({g[a].size(), a});
        }
        if(g[b].size() != 0) {
            st.insert({g[b].size(), b});
        }
    };

    auto getClique = [&st](int x) {
        int sz = g[x].size();
        vector<int> vert = {};
        cerr << "from x " << x << ": ";
        for(auto it : g[x]) {
            vert.push_back(it);
            cerr << it << " ";
        }
        cerr << endl;


        forn(sz) {
            fill(adj[i], adj[i] + (1 << sz), false);
            adj[i][0] = true;
            for(int mask = 1; mask < (1 << sz); mask ++) {
                adj[i][mask] = adj[i][mask & (mask - 1)] & (g[vert[i]].find(vert[pw[mask - (mask & (mask - 1))]]) != g[vert[i]].end());
            }
        }
        int ret = 0;

        fill(can, can + (1 << sz), false);
        can[0] = true;

        forn(1 << sz) {
            can[i] = can[i & (i - 1)] & adj[pw[i - (i & (i - 1))]][i & (i - 1)];
            if(can[i]) {
                chkmax(ret, __builtin_popcount(i));
            }
        }
        return ret + 1;
    };

    int ret = 1;

    while(!st.empty()) {
        auto curr = st.begin(); st.erase(curr);
        auto vert = (*curr).second;

        cerr << "Trying vert " << vert << endl;
        chkmax(ret, getClique(vert));
        cerr << "Remove vert " << endl;

        vector<int> toRem = {};
        for(auto it : g[vert]) {toRem.push_back(it);}

        for(auto it : toRem) {
            rmEdge(vert, it);
        }
    }
    return ret;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    for(int i = 0, j = 1; i < MAX_K; i ++, j *= 2) {
        pw[j] = i;
    }

    cin >> n >> k;
    forn(n) {
        int d;
        cin >> d;
        while(d --) {
            int b;
            cin >> b;
            g[i].insert(b);
        }
    }

    cout << solve() << endl;
    return 0;
}

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