제출 #1363400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1363400		nguyenkhangninh99	Political Development (BOI17_politicaldevelopment)	C++20	100 / 100	480 ms	332300 KiB

politicaldevelopment

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

const int maxn = 5e4 + 5;
bitset<maxn> bs[maxn];
set<int> g[maxn];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, k; cin >> n >> k;
    for(int i = 0; i < n; i++){
        int d; cin >> d;
        while(d--){
            int j; cin >> j;
            g[i].insert(j);
            bs[i][j] = 1;
        }
        bs[i][i] = 1;
    }  

    int ans = 1;
    set<pair<int, int>> s;
    for(int i = 0; i < n; i++) s.insert({g[i].size(), i});

    while(s.size()){
        int id = (*s.begin()).second;
        s.erase(*s.begin());

        for(int j: g[id]){
            s.erase({g[j].size(), j});
            g[j].erase(id);
            s.insert({g[j].size(), j});
        }

        vector<int> cur(g[id].begin(), g[id].end());
        for(int j = 0; j < (1 << cur.size()); j++){
            vector<int> anne;
            anne.push_back(id);
            for(int c = 0; c < cur.size(); c++){
                if(j & (1 << c)) anne.push_back(cur[c]);
            }
            bool ok = 1;
            for(int x: anne) for(int y: anne) ok &= (bs[x][y]);
            if(ok) ans = max(ans, (int)anne.size());
        }
    }

    cout << ans;
}

• 서브태스크 1: 4 / 4
• 서브태스크 2: 12 / 12
• 서브태스크 3: 23 / 23
• 서브태스크 4: 38 / 38
• 서브태스크 5: 23 / 23