Submission #1293660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293660		Hamed_Ghaffari	Political Development (BOI17_politicaldevelopment)	C++20	100 / 100	319 ms	17132 KiB

politicaldevelopment

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

using pii = pair<int, int>;

#define X first
#define Y second
#define SZ(x) int(x.size())

const int MXN = 5e4+5;

int n, k, deg[MXN], ans, dp[MXN], adj[MXN];
bool mark[MXN];
vector<int> g[MXN];
set<pii> st, edges;

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> k;
    for(int i=0,d; i<n; i++) {
        cin >> d;
        g[i].resize(d);
        for(int &j : g[i]) {
            cin >> j;
            if(j>i) deg[i]++, deg[j]++, edges.insert({min(i, j), max(i, j)});
        }
    }
    for(int i=0; i<n; i++) st.insert({deg[i], i});
    while(!st.empty()) {
        int v = st.begin()->Y;
        st.erase(st.begin());
        mark[v] = 1;
        vector<int> vec = {v};
        for(int u : g[v]) if(!mark[u]) {
            st.erase({deg[u], u});
            st.insert({--deg[u], u});
            vec.push_back(u);
        }
        for(int i=0; i<SZ(vec); i++) adj[i] = 0;
        for(int i=0; i<SZ(vec); i++)
            for(int j=i+1; j<SZ(vec); j++)
                if(edges.find({min(vec[i], vec[j]), max(vec[i], vec[j])})!=edges.end())
                    adj[i] |= 1<<j,
                    adj[j] |= 1<<i;
        dp[0] = 1;
        for(int msk=1; msk<(1<<SZ(vec)); msk++) {
            int v = __lg(msk);
            dp[msk] = dp[msk^(1<<v)] & ((msk&(adj[v]|(1<<v)))==msk);
            if(dp[msk]) ans = max(ans, __builtin_popcount(msk));
        }
    }
    cout << ans << '\n';
    return 0;
}

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