Submission #889593

#	Time	Username	Problem	Language	Result	Execution time	Memory
889593		zeta7532	Political Development (BOI17_politicaldevelopment)	C++17	0 / 100	3069 ms	29268 KiB

politicaldevelopment

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)

int main() {
    ll N,K;
    cin >> N >> K;
    vector<set<ll>> s(N);
    set<pair<ll,ll>> S;
    rep(i,N){
        ll D;
        cin >> D;
        rep(j,D){
            ll x;
            cin >> x;
            s[i].insert(x);
        }
        s[i].insert(i);
        S.insert({D+1,i});
    }
    ll ans=0;
    while(S.size()!=0){
        auto it=*S.begin();
        S.erase(it);
        ll sz=it.fi;
        ll i=it.se;
        vector<ll> A(sz);
        auto itr=s[i].begin();
        ll cnt=0;
        while(itr!=s[i].end()){
            A[cnt]=*itr;
            itr++;
            cnt++;
        }
        rep(bit,1<<sz){
            bool ok=true;
            ll l=sz;
            rep(j,sz){
                if(bit&(1<<j)) l--;
                rep(k,sz){
                    if(bit&(1<<j)) continue;
                    if(bit&(1<<k)) continue;
                    if(s[A[j]].find(A[k])==s[A[j]].end()) ok=false;
                }
            }
            if(ok) ans=max(ans,l);
        }
    }
    cout << ans << endl;
    return 0;
}

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