Submission #1304039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304039		mocha	Political Development (BOI17_politicaldevelopment)	C++20	100 / 100	376 ms	314100 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;
const int mx = 5e4+5;

int n, k;
bitset<mx> a[mx];
vector<int> g[mx];
int deg[mx];
set<pair<int, int>> st;
int cnt;
int c[mx];
int b[mx];
int ans = 0;
bool vis[mx];

void dfs(int id, int mask, int ner) {
    if (id == cnt) {
        ans = max(ans, __builtin_popcount(mask));
        return;
    }
    if ((ner & (1<<id)) and (b[id] & mask) == mask) {
        dfs(id+1, mask | (1<<id), (ner & b[id]));
    }
    dfs(id+1, mask, ner);
}

signed main() {
    cin >> n >> k;
    for (int i=0;i<n;i++) {
        int d;
        cin >> d;
        deg[i] = d;
        st.insert({deg[i], i});
        for (int j=0;j<d;j++) {
            int x;
            cin >> x;
            a[i][x] = 1;
            g[i].push_back(x);
        }
    }
    while (st.size()) {
        auto [it, u] = *st.begin(); st.erase(st.begin());
        vis[u] = 1;
        c[0] = u;
        cnt = 1;
        for (int v:g[u]) {
            if (vis[v]) continue;
            st.erase({deg[v], v});
            deg[v]--;
            st.insert({deg[v], v});
            c[cnt++] = v;
        }
        assert(cnt <= 15);
        for (int i=0;i<cnt;i++) {
            b[i] = 0;
            for (int j=0;j<cnt;j++) {
                if (a[c[i]][c[j]]) {
                    b[i] |= 1<<j;
                }
            }
        }
        dfs(1, 1, b[0]);
    }
    cout << ans << "\n";
}

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