Submission #830636

#	Time	Username	Problem	Language	Result	Execution time	Memory
830636		Johann	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	249 ms	27564 KiB

politicaldevelopment

// gets sub1+sub2
#include <bits/stdc++.h>

using namespace std;

#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define F0R(i, n) for (int i = 0; i < (n); ++i)
#define tiii tuple<int,int,int>
#define vtiii vector<tiii>


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N, K;
    cin >> N >> K;
    vector<set<int>> adj(N);
    vi d(N);
    vb active(N, true);
    queue<int> q;
    F0R(i, N) {
        int u;
        cin >> d[i];
        F0R(j, d[i]) cin >> u, adj[i].insert(u);
        if (d[i] < K) q.push(i);
    }

    int res = 1;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        if (!active[v]) continue;

        vi neig;
        for (int u: adj[v]) {
            if (active[u]) {
                neig.push_back(u);
            }
        }
        vi bm(sz(neig));
        for (int i = 0; i < sz(neig); ++i) {
            bm[i] = 1 << i;
            for (int j = 0; j < sz(neig); ++j) {
                if (adj[neig[i]].find(neig[j]) != adj[neig[i]].end()) {
                    bm[i] |= 1 << j;
                }
            }
        }

        for (int sel = 0; sel < (1 << sz(neig)); ++sel) {
            int m = sel;
            for (int i = 0; i < sz(neig); ++i) {
                if ((sel & (1 << i)) > 0) {
                    m &= bm[i];
                }
            }
            res = max(res, __builtin_popcount(m) + 1);
        }

        active[v] = false;
        for (int u: neig) {
            --d[u];
            if (d[u] < K) q.push(u);
        }
    }
    cout << res << endl;
}

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