제출 #1268878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268878		Davdav1232	Political Development (BOI17_politicaldevelopment)	C++20	100 / 100	394 ms	26248 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> vii;
typedef long long ll;
int INF=1e9;

int main() {
    int N, K;
    cin>>N>>K;
    vector<set<int>> D(N);
    for(int i=0; i<N; i++){
        int d;
        cin>>d;
        for(int j=0; j<d; j++){
            int a;
            cin>>a;
            D[i].insert(a);
        }
    }
    int ans=1;
    set<vii> degree;
    for(int i=0; i<N; i++) degree.insert({D[i].size(), i});
    for(int t=N; t; t--){
        if(ans==K){
            break;
        }
        vii x=*degree.begin();
        degree.erase(x);
        //find all of the friends of x
        vi friends;
        for(auto y : D[x.second]){
            friends.push_back(y);
        }
        int d=friends.size();
        for(int i=0; i<d; i++){
            D[friends[i]].erase(x.second);
            degree.erase({D[friends[i]].size()+1, friends[i]});
            degree.insert({D[friends[i]].size(), friends[i]});
        }
        if(d==0) continue;
        if(d==1){
            ans=max(ans, 2);
            continue;
        }
        vector<vector<bool>> r(d, vector<bool> (d, 0));
        for(int i=0; i<d; i++){
            for(int j=i+1; j<d; j++){
                if(D[friends[i]].count(friends[j])==1){
                    r[i][j]=1;
                    r[j][i]=1;
                }
            }
        }
        for(int i=1; i<(1<<d); i++){
            if(__builtin_popcount(i)+1<=ans) continue;
            int p=i;
            vector<int> w;
            int q=0;
            while(p>0){
                if(p%2==1){
                    w.push_back(q);
                }
                p/=2;
                q++;
            }
            bool works=1;
            for(int j=0; j<w.size(); j++){
                for(int k=j+1; k<w.size(); k++){
                    if(!r[w[j]][w[k]]){
                        works=0;
                        j=1e9;
                        k=1e9;
                    }
                }
            }
            if(works) ans=w.size()+1;
        }
    }
    cout<<ans;
    return 0;
}

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