Submission #1306268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306268		zxzuam	Political Development (BOI17_politicaldevelopment)	C++20	0 / 100	38 ms	3856 KiB

politicaldevelopment

#include <bits/stdc++.h>
#define int int64_t
using namespace std;
constexpr int MAXN = 50009, inf = 1e18;
set <int> g[MAXN];
vector <int> cand[MAXN];
void solve() {
    int n, k;
    cin >> n >> k;
    set <pair <int, int>> s;
    for(int i = 1; i <= n; i++) {
        int d;
        cin >> d;
        for(int j = 0; j < d; j++) {
            int x;
            cin >> x;
            x++;
            g[i].insert(x);
        }
        s.insert({ d, i });
    }
    vector <bool> used(n + 1, 1);
    int ans = 1;
    for(auto [_, v] : s) {
        used[v] = 0;
        cand[ v ].emplace_back(v);
        for(auto to : g[v]) {
            if( used[to] ) {
                cand[ v ].emplace_back(to);
            }
        }
    }
    vector <int> vv;
    for(int v = 1; v <= n; v++) {
        swap(vv, cand[v]);
        int sz = (int)vv.size();
        fill(used.begin(), used.end(), 1);
        int mx = 1;
        for(int bt = 0; bt < (1 << sz); bt++) {
            if(!used[bt] ) continue;
            int cnt = sz;
            for(int i = 0; i < sz; i++) {
                if( !((bt >> i) & 1) ) {
                    for(int j = 0; j < sz; j++) {
                        if( (bt >> j) & 1 ) {
                            if( !g[ vv[i] ].count(vv[j]) || !g[vv[j]].count(vv[i]) ) {
                                used[ ( bt | (1 << i) ) ] = 0;
                            }
                        }
                    }
                    cnt--;
                }
            }
            mx = max(mx, cnt);
        }
        ans = max(ans, mx);
    }
    cout << ans;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("7-router.in", "r", stdin);
    //freopen("7-router.out.txt", "w", stdout);
    int tt = 1;
    //cin >> tt;
    while (tt--){
        solve();
    }
}

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