제출 #1172282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172282		crafticat	Political Development (BOI17_politicaldevelopment)	C++20	77 / 100	3094 ms	26248 KiB

politicaldevelopment

#include <bits/stdc++.h>

using namespace std;


#define F0R(i, n) for (int i= 0 ; i< n;i++)
#define FOR(i,j,n) for (int i = j; i< n;i++)

template<typename T>
using V = vector<T>;
using vi = V<int>;
using pi = pair<int,int>;

int solve(V<set<int>> g) {
    int ans = 0;

    F0R(i, 1 << g.size()) {
        bitset<20> b = i;
        bool pos = true;

        F0R(j, g.size()) {
            F0R(k, g.size()) {
                if (b[j] and b[k] and !g[j].contains(k) and j != k) {
                    pos = false;
                    break;
                }
            }
            if (!pos) break;
        }
        if (pos)
            ans = max(ans,(int) b.count());
    }
    return ans;
}

int main() {
    int n, k; cin >> n >> k;

    V<set<int>> g(n);
    set<pi> pq;

    F0R(i, n) {
        int d; cin >> d;
        F0R(j, d) {
            int y; cin >> y;
            g[i].insert(y);
        }
    }
    F0R(i, n) {
        for (auto y : g[i]) {
            if (!g[y].count(i)) exit(5);
        }
    }

    F0R(i, n) {
        pq.insert({g[i].size(), i});
    }

    int ans = 0;
    while (!pq.empty()) {
        auto [am, node] = *pq.begin(); pq.erase(pq.begin());

        V<set<int>> miniG(g[node].size() + 1);
        map<int, int> decompose;
        decompose[node] = 0;
        int nextId = 1;

        for (auto y : g[node])
            decompose[y] = nextId++;

        // todo optimize this loop
        for (auto y : g[node]) {
            for (auto z : g[y]) {
                if (!decompose.count(z)) continue;
                miniG[decompose[y]].insert(decompose[z]);
            }
            miniG[0].insert(decompose[y]);
        }

        ans = max(ans, solve(miniG));

        for (auto y : g[node]) {
            pq.erase({g[y].size(), y});
            g[y].erase(node);
        }

        for (auto y : g[node]) {
            pq.insert({g[y].size(), y});
        }
        g[node].clear();
    }

    cout << ans;
}

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