Submission #676698

#	Time	Username	Problem	Language	Result	Execution time	Memory
676698		bogdanvladmihai	Political Development (BOI17_politicaldevelopment)	C++14	0 / 100	2 ms	980 KiB

politicaldevelopment

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

int main() {
    int N, K; cin >> N >> K;
    vector<set<int>> G(N), T(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(x);
            T[x].insert(i);
        }
    }

    set<pair<int, int>> q;
    for (int i = 0; i < N; i++) {
        q.insert(make_pair((int)G[i].size(), i));
    }

    int answer = 1;
    while (!q.empty()) {
        int u = q.begin() -> second;
        q.erase(q.begin());

        int size = (int)G[u].size();
        for (int subset = 1; subset < (1 << size); 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 && clique; i++) {
                for (int j = i + 1; j < (int)nodes.size() && clique; j++) {
                    if (G[i].find(j) == G[i].end() || G[j].find(i) == G[j].end()) {
                        clique = false;
                    }
                }
            }
            if (clique) {
                answer = max(answer, (int)nodes.size());
            }
        }


        for (const int &x : T[u]) {
            if ((int)G[x].size() > 0) {
                q.erase(make_pair((int)G[x].size(), x));
                G[x].erase(u);
                q.insert(make_pair((int)G[x].size(), x));
            }
        }

        G[u].clear();
    }
    
    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