Submission #981804

#	Time	Username	Problem	Language	Result	Execution time	Memory
981804		Ghulam_Junaid	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	346 ms	28576 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;
 
const int N = 5e4 + 10;
int n, k;
unordered_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 = 0; 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: 38 / 38
• Subtask 5: 23 / 23