Submission #244623

#	Time	Username	Problem	Language	Result	Execution time	Memory
244623		kimbj0709	Political Development (BOI17_politicaldevelopment)	C++14	0 / 100	3085 ms	23928 KiB

politicaldevelopment

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define maxn 50050
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int no_of_people,k;
    int no_of_input1;
    int input;
    cin >> no_of_people >> k;
    vector<set<int> > adj(maxn);
    bool can2 = 0;
    for(int i=0;i<no_of_people;i++){
        cin >> no_of_input1;
        for(int j=0;j<no_of_input1;j++){
            cin >> input;
            adj[i].insert(input);
        }
    }
    int ans = 1;
    for(int i=0;i<no_of_people;i++){
        for(int j=0;j<pow(2,adj[i].size());j++){
            vector<int> temp;
            if(__builtin_popcount(j)>=k||__builtin_popcount(j)+1<=ans){
                continue;
            }
            int cnt = 0;
            for(auto kk:adj[i]){
                if(j&(1<<cnt)){
                    if(kk<i){
                        goto cont2;
                    }
                    temp.push_back(kk);
                }
                cnt++;
            }
            temp.push_back(i);
            /*for(auto kk:temp){
                cout << kk << " ";
            }
            cout << "\n---------\n";*/
            for(int a=0;a<temp.size();a++){
                for(int b=0;b<temp.size();b++){
                    if(a==b){
                        continue;
                    }
                    if(adj[temp[a]].find(temp[b])==adj[temp[a]].end()){
                        goto cont;
                    }
                }
            }
            //cout << "YES" << " " << temp.size() << "\n";
            ans = max(ans,(int)temp.size());
            cont : ;
            cont2: ;
        }

    }
    cout << min(k,ans);

}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int32_t main()':
politicaldevelopment.cpp:43:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int a=0;a<temp.size();a++){
                         ~^~~~~~~~~~~~
politicaldevelopment.cpp:44:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int b=0;b<temp.size();b++){
                             ~^~~~~~~~~~~~
politicaldevelopment.cpp:13:10: warning: unused variable 'can2' [-Wunused-variable]
     bool can2 = 0;
          ^~~~

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