Submission #677040

#	Time	Username	Problem	Language	Result	Execution time	Memory
677040		Cyanmond	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	427 ms	31432 KiB

politicaldevelopment

#include <bits/stdc++.h>

int main() {
    int N, K;
    std::cin >> N >> K;
    std::vector<int> D(N);
    std::vector<std::vector<int>> E(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> D[i];
        E[i].resize(D[i]);
        for (auto &e : E[i]) {
            std::cin >> e;
        }
    }

    int answer = 0;

    //if (N <= 5000 or K <= 5) {
        // Group 1, 2, 4, 5
        // Group 3 ... Time Limit ?
        std::vector<std::unordered_set<int>> S(N);
        for (int i = 0; i < N; ++i) {
            for (auto &e : E[i]) {
                S[i].insert(e);
            }
        }

        std::set<std::pair<int, int>> group_size;
        for (int i = 0; i < N; ++i) {
            group_size.insert({D[i], i});
        }

        while (not group_size.empty()) {
            const auto [s, f] = *group_size.begin();
            group_size.erase(group_size.begin());

            // step 1 : brute force
            assert(s < K);
            std::vector<std::vector<bool>> table(s, std::vector<bool>(s));
            int i1 = 0;
            for (const int e : S[f]) {
                int i2 = 0;
                for (const int e2 : S[f]) {
                    if (S[e].find(e2) != S[e].end()) {
                        table[i1][i2] = true;
                    }
                    ++i2;
                }
                ++i1;
            }

            std::vector<bool> dp(1 << s);
            dp[0] = true;
            for (int state = 0; state < (1 << s); ++state) {
                if (not dp[state]) {
                    continue;
                }
                answer = std::max(answer, __builtin_popcount(state) + 1);
                for (int new_bit = 0; new_bit < s; ++new_bit) {
                    if ((state & (1 << new_bit)) or dp[state | (1 << new_bit)]) {
                        continue;
                    }
                    bool ok = true;
                    for (int i = 0; i < s; ++i) {
                        if (state & (1 << i)) {
                            if (not table[i][new_bit]) {
                                ok = false;
                                break;
                            }
                        }
                    }
                    if (ok) {
                        dp[state | (1 << new_bit)] = true;
                    }
                }
            }

            // step 2 : update
            for (const int e : S[f]) {
                S[e].erase(f);
                const auto itr = group_size.find({D[e], e});
                group_size.erase(itr);
                group_size.insert({--D[e], e});
            }
        }

        std::cout << answer << std::endl;
    //}
}

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