Submission #1047035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047035		12345678	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	509 ms	28916 KiB

politicaldevelopment

#include <bits/stdc++.h>

using namespace std;

const int nx=5e4+5;

int n, k, x, y, res;
set<int> d[nx];
set<pair<int, int>> s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=0; i<n; i++)
    {
        cin>>x;
        for (int j=1; j<=x; j++) cin>>y, d[i].insert(y);
        s.insert({d[i].size(), i});
    }
    while (!s.empty())
    {
        auto [sz, x]=*s.begin();
        //cout<<"debug "<<s.size()<<' '<<sz<<' '<<x<<'\n';
        s.erase(s.begin());
        vector<int> v;
        //cout<<"node ";
        for (auto tmp:d[x]) v.push_back(tmp);//cout<<tmp<<' ';
        //cout<<'\n';
        for (int msk=0; msk<(1<<sz); msk++)
        {
            vector<int> t;
            for (int i=0; i<sz; i++) if (msk&(1<<i)) t.push_back(v[i]);
            int cnt=__builtin_popcount(msk);
            bool can=1;
            for (int i=0; i<cnt; i++) for (int j=i+1; j<cnt; j++) if (d[t[i]].find(t[j])==d[t[i]].end()) can=0;
            if (can) res=max(res, cnt+1);
        }
        for (auto tmp:d[x]) s.erase(make_pair(d[tmp].size(), tmp)), d[tmp].erase(x), s.insert({d[tmp].size(), tmp});
    }
    cout<<res;
}

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