Submission #676447

#	Time	Username	Problem	Language	Result	Execution time	Memory
676447		bogdanvladmihai	Political Development (BOI17_politicaldevelopment)	C++14	0 / 100	7 ms	2012 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K; cin >> N >> K;
    vector<set<int>> G(N);
    for (int i = 0; i < N; i++) {
        int nei; cin >> nei;
        for (int j = 0; j < nei; j++) {
            int x; cin >> x;
            G[i].insert(j);
        }
    }

    priority_queue<pair<int, int>> deg;
    for (int u = 0; u < N; u++) {
        deg.push(make_pair(-(int)G[u].size(), u));
    }

    vector<bool> used(N);
    int answer = 1;
    while (!deg.empty()) {
        int u = deg.top().second;
        deg.pop();

        vector<int> toRemove;
        for (const int &x : G[u]) {
            if (used[x]) {
                toRemove.push_back(x);
            }
        }
        for (const int &x : toRemove) {
            G[u].erase(x);
        }

        int maxSize = (int)G[u].size();
        assert(maxSize < K);
        for (int subset = 0; subset < (1 << maxSize); subset++) {
            vector<int> nodes;
            nodes.push_back(u);
            int id = 0;
            for (const int &v : G[u]) {
                if ((subset & (1 << id)) > 0) {
                    nodes.push_back(v);
                }
                id++;
            }

            bool clique = true;
            for (int i = 0; i < (int)nodes.size() - 1; i++) {
                for (int j = i + 1; j < (int)nodes.size(); j++) {
                    int u = nodes[i], v = nodes[j];
                    if (G[u].find(v) == G[u].end() || G[v].find(u) == G[v].end()) {
                        clique = false;
                    }
                }
            }
            if (clique) {
                answer = max(answer, (int)nodes.size());
            }
        }
        
        used[u] = true;
    }
    
    cout << answer << "\n";
    return 0;
}

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