Submission #889591

#	Time	Username	Problem	Language	Result	Execution time	Memory
889591		shiomusubi496	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	381 ms	28876 KiB

politicaldevelopment

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(v) begin(v), end(v)

int main() {
    int n, k; cin >> n >> k;
    vector<unordered_set<int>> g(n);
    rep (i, n) {
        int d; cin >> d;
        rep (j, d) {
            int a; cin >> a;
            g[i].insert(a);
        }
    }
    vector<int> deg(n);
    vector<bool> used(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
    rep (i, n) {
        deg[i] = g[i].size();
        que.emplace(deg[i], i);
    }
    int ans = 0;
    while (!que.empty()) {
        auto [d, v] = que.top(); que.pop();
        if (deg[v] != d) continue;
        vector<int> a;
        for (auto i : g[v]) {
            if (used[i]) continue;
            a.push_back(i);
        }
        int m = a.size();
        rep (bt, 1 << m) {
            vector<int> b;
            rep (i, m) if (bt >> i & 1) b.push_back(a[i]);
            rep (i, b.size()) rep (j, i) {
                if (g[b[i]].count(b[j]) == 0) goto END;
            }
            ans = max(ans, __builtin_popcount(bt) + 1);
            END:;
        }
        used[v] = true;
        for (auto i : g[v]) {
            if (used[i]) continue;
            --deg[i];
            que.emplace(deg[i], i);
        }
    }
    cout << ans << endl;
}

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