제출 #1306270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306270		zxzuam	Political Development (BOI17_politicaldevelopment)	C++20	0 / 100	3 ms	3132 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();
        int mx = 1;
        vector <int> daun;
        for(int bt = 0; bt < (1 << sz); bt++) {
            if(!used[bt] ) continue;
            daun.clear();
            int cnt = 0;
            for(int i = 0; i < sz; i++) {
                if( ((bt >> i) & 1) ) {
                    cnt++;
                    daun.emplace_back(vv[i]);
                }
            }
            bool ok = 1;
            for(int i = 0; i < cnt; i++) {
                int u = daun[i];
                for(int j = i + 1; j < cnt; j++) {
                    int v = daun[j];
                    if(!g[u].count(v) || !g[v].count(u)) {
                        ok = 0;
                        break;
                    }
                }
                if(!ok) break;
            }
            if(ok){
            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