Submission #1047035

#TimeUsernameProblemLanguageResultExecution timeMemory
104703512345678Political Development (BOI17_politicaldevelopment)C++17
100 / 100
509 ms28916 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...