Submission #1117555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117555		stefanneagu	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	711 ms	333672 KiB

politicaldevelopment

#include <bits/stdc++.h>

using namespace std;

const int nmax = 5e4 + 2;

set<int> adj[nmax];
bitset<nmax> f[nmax];
int ans = 0;

void calc(int i) {
  for(int bit = 0; bit < (1 << adj[i].size()); bit++) {
    vector<int> v;
    auto pl = adj[i].begin();
    for(int x = 0; (1 << x) <= bit; x++) {
      if(bit & (1 << x)) {
        v.push_back(*pl);
      }
      pl++;
    }
    v.push_back(i);
    bool ok = 1;
    for(auto it : v) {
      for(auto it2 : v) {
        if(it != it2 && f[it][it2] == 0) {
          ok = 0;
          break;
        }
      }
      if(!ok) {
        break;
      }
    }
    if(ok) {
      ans = max(ans, (int) v.size());
    }
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  for(int i = 1; i <= n; i++) {
    int d;
    cin >> d;
    while(d--) {
      int j;
      cin >> j;
      j++;
      adj[i].insert(j);
      f[i][j] = 1;
    }
  }
  set<pair<int, int>> noduri;
  for(int i = 1; i <= n; i++) {
    noduri.insert({adj[i].size(), i});
  }
  for(int _ = 1; _ <= n; _++) {
    pair<int, int> top = *noduri.begin();
    int i = top.second;
    calc(i);
    // cout << i << " ";
    noduri.erase({adj[i].size(), i});
    for(auto it : adj[i]) {
      noduri.erase({adj[it].size(), it});
      adj[it].erase(i);
      noduri.insert({adj[it].size(), it});
    }
  }
  cout << ans;
  return 0;
}

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