Submission #758389

#	Time	Username	Problem	Language	Result	Execution time	Memory
758389		joelgun14	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	1053 ms	33228 KiB

politicaldevelopment

#include <bits/stdc++.h>
#define endl "\n"
#define fi first
#define se second
using namespace std;
const int lim = 2e5 + 5;
set<int> edges[lim];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    // fi -> cnt
    // se -> num
    set<pair<int, int>> s;
    for(int i = 0; i < n; ++i) {
        int d;
        cin >> d;
        for(int j = 0; j < d; ++j) {
            int x;
            cin >> x;
            edges[i].insert(x);
        }
        s.insert({d, i});
    }
    int mx = 0;
    //cout << "TEST" << endl;
    while(s.size()) {
        // smallest cnt
        // id nya sembarang
        int sz = (*s.begin()).fi, id = (*s.begin()).se;
        //cout << sz << " "<< id << endl;
        s.erase(s.begin());
        // nah berarti proses node ke id
        vector<int> adj;
        for(auto i : edges[id])
            adj.push_back(i);
        for(int i = 0; i < (1 << adj.size()); ++i) {
            vector<int> nodes = {id};
            for(int j = 0; j < adj.size(); ++j) {
                if((1 << j) & i) {
                    nodes.push_back(adj[j]);
                }
            }
            bool ans = 1;
            for(int j = 0; j < nodes.size(); ++j) {
                for(int k = j + 1; k < nodes.size(); ++k) {
                    if(!edges[nodes[j]].count(nodes[k])) {
                        ans = 0;
                    }
                }
            }
            if(ans)
                mx = max(mx, (int)nodes.size());
        }
        for(auto i : adj) {
            s.erase(s.find({edges[i].size(), i}));
            edges[i].erase(edges[i].find(id));
            s.insert({edges[i].size(), i});
        }
        edges[id].clear();
    }
    cout << mx << endl;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:39:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             for(int j = 0; j < adj.size(); ++j) {
      |                            ~~^~~~~~~~~~~~
politicaldevelopment.cpp:45:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for(int j = 0; j < nodes.size(); ++j) {
      |                            ~~^~~~~~~~~~~~~~
politicaldevelopment.cpp:46:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |                 for(int k = j + 1; k < nodes.size(); ++k) {
      |                                    ~~^~~~~~~~~~~~~~
politicaldevelopment.cpp:30:13: warning: unused variable 'sz' [-Wunused-variable]
   30 |         int sz = (*s.begin()).fi, id = (*s.begin()).se;
      |             ^~

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