Submission #550440

#	Time	Username	Problem	Language	Result	Execution time	Memory
550440		Jarif_Rahman	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	865 ms	28380 KiB

politicaldevelopment

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, k;
int ans = 0;
vector<unordered_set<int>> v;
vector<int> nodes;
vector<int> ss;
set<pair<int,int>> deg;

void bf(int in){
    if(in == nodes.size()){
        bool ok = 1;
        for(int i = 0; i < ss.size(); i++) for(int j = i+1; j < ss.size(); j++)
            if(v[ss[i]].find(ss[j]) == v[ss[i]].end()) ok = 0;
        if(ok) ans = max(ans, int(ss.size()));
        return;
    }
    ss.pb(nodes[in]);
    bf(in+1);
    ss.pop_back();
    bf(in+1);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    v.resize(n);

    for(int i = 0; i < n; i++){
        int d; cin >> d;
        while(d--){
            int x; cin >> x;
            v[i].insert(x);
        }
    }

    for(int i = 0; i < n; i++) deg.insert({v[i].size(), i});

    while(!deg.empty()){
        auto [s, i] = *deg.begin();
        deg.erase(deg.begin());
        nodes.pb(i);
        for(int x: v[i]) nodes.pb(x);
        bf(0);
        nodes.clear();
        for(int x: v[i]){
            deg.erase(make_pair(int(v[x].size()), x));
            v[x].erase(i);
            deg.insert(make_pair(int(v[x].size()), x));
        }
    }

    cout << ans << "\n";
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'void bf(int)':
politicaldevelopment.cpp:17:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     if(in == nodes.size()){
      |        ~~~^~~~~~~~~~~~~~~
politicaldevelopment.cpp:19:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for(int i = 0; i < ss.size(); i++) for(int j = i+1; j < ss.size(); j++)
      |                        ~~^~~~~~~~~~~
politicaldevelopment.cpp:19:63: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for(int i = 0; i < ss.size(); i++) for(int j = i+1; j < ss.size(); j++)
      |                                                             ~~^~~~~~~~~~~

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