Submission #550259

#	Time	Username	Problem	Language	Result	Execution time	Memory
550259		OttoTheDino	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	405 ms	28780 KiB

politicaldevelopment

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

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (int i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
#define sz(a)                       (int)a.size()
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

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

    int n, K, ans = 1; cin >> n >> K;

    set<int> adj[n+1];
    set<ii> st;

    rep (i,1,n) {
        int d; cin >> d;
        rep (j,1,d) {
            int v; cin >> v;
            adj[i].insert(v+1);
        }
    }

    rep (i,1,n) st.insert({adj[i].size(), i});

    while (!st.empty()) {
        auto it = st.begin();
        int sz = (*it).fi+1, u = (*it).se;
        st.erase(it);

        vi bois;
        bois.pb(u);
        for (int v : adj[u]) bois.pb(v);

        while (true) {
            bool suc = 0;
            rep (i,0,(1<<sz)-1) {
                if (__builtin_popcount(i)==ans+1) {
                    bool suc2 = 1;
                    rep (j,0,sz-1) {
                        if (!(i&(1<<j))) continue;
                        rep (k,j+1,sz-1) {
                            if (!(i&(1<<k))) continue;
                            if (adj[bois[j]].find(bois[k])==adj[bois[j]].end()) {
                                suc2 = 0;
                                goto out;
                            }
                        }
                    } 
                    out:
                    if (suc2) {
                        suc = 1;
                        break;
                    }
                }
            }

            if (suc) ++ans;
            else break;
        }

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

    cout << ans << "\n";

    return 0;
}

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