Submission #553154

#	Time	Username	Problem	Language	Result	Execution time	Memory
553154		Talha_Taki	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	1113 ms	28760 KiB

politicaldevelopment

#include <bits/stdc++.h>
 
using namespace std;
 
 
typedef long long ll;
typedef pair <int, int> pii;
 
 
int main(const int argc, const char *argv[]) {
 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector <set <int>> adj(n);
    set <pii> S;

    for(int i = 0; i < n; ++i) {
        int d;
        cin >> d;

        for(int j = 0; j < d; ++j) {
            int x;
            cin >> x;

            adj[i].insert(x);
        }
        S.insert({d, i});
    }

    int ans = 1;

    while (!S.empty()) {
        int u = (*S.begin()).second;
        S.erase(S.begin());

        vector <int> node;
        node.push_back(u);
        for(int x : adj[u]) {
            node.push_back(x);
        }

        int d = node.size();
        for(int i = 1; i < 1<<d; ++i) {
            vector <int> tmp;
            for(int j = 0; j < d; ++j) {
                if (i&(1<<j)) tmp.push_back(node[j]);
            }
            bool flag = true;
            int size = tmp.size();

            for(int j = 0; flag && j < size; ++j) {
                for(int k = j+1; flag && k < size; ++k) {
                    if (adj[tmp[j]].find(tmp[k]) == adj[tmp[j]].end()) flag = false;
                }
            }

            if (flag) ans = max(ans, size);
        }

        for(int i = 1; i < d; ++i) {
            int x = node[i];
            S.erase({adj[x].size(), x});
            adj[x].erase(u);
            S.insert({adj[x].size(), x});
        }
    }


    cout << ans;
 
 
    return 0;
}

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