Submission #1304031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304031		mocha	Political Development (BOI17_politicaldevelopment)	C++20	0 / 100	3093 ms	21548 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;

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());
        c[0] = u;
        cnt = g[u].size()+1;
        for (int i=0;i<g[u].size();i++) {
            c[i+1] = g[u][i];
        }
        for (int i=0;i<cnt;i++) {
            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: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 38
• Subtask 5: 0 / 23