Submission #924422

#	Time	Username	Problem	Language	Result	Execution time	Memory
924422		Ghulam_Junaid	Political Development (BOI17_politicaldevelopment)	C++17	39 / 100	349 ms	26448 KiB

politicaldevelopment

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

const int N = 5e4 + 10;
int n, k;
set<int> g[N];
set<pair<int, int>> st;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;

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

        for (int j = 0; j < x; j ++){
            int v;
            cin >> v;
            g[i].insert(v);
        }

        st.insert({x, i});
    }

    int ans = 1;
    while (!st.empty()){
        auto p = *st.begin();
        st.erase(st.begin());

        int v = p.second;

        vector<int> possible;
        for (int u : g[v])
            possible.push_back(u);

        int sz = possible.size();

        for (int mask = 1; mask < (1 << sz); mask ++){
            vector<int> appeared;       
            bool good = 1;     
            for (int i = 0; i < sz; i ++){
                if ((1 << i) & mask == 0) continue;

                bool all = 1;
                for (int x : appeared)
                    if (g[possible[i]].find(x) == g[possible[i]].end())
                        all = 0;

                if (!all){
                    good = 0;
                    break;
                }

                appeared.push_back(possible[i]);
            }

            if (good)
                ans = max(ans, (int)appeared.size() + 1);
        }

        for (int u : possible){
            st.erase({g[u].size(), u});
            g[u].erase(v);
            st.insert({g[u].size(), u});
        }
    }

    cout << ans << endl;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:45:37: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   45 |                 if ((1 << i) & mask == 0) continue;
      |                                ~~~~~^~~~

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