Submission #223837

#	Time	Username	Problem	Language	Result	Execution time	Memory
223837		jk_	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	193 ms	9960 KiB

politicaldevelopment

#include <bits/stdc++.h>  // score: 100
using namespace std;

int clique_n;
array<bitset<10>, 10> adjmat;
uint32_t mask;
uint32_t popcount;
int largest_clique(int i) {
  if (i == clique_n)
    return popcount;
  int best = largest_clique(i+1);  // skip i

  if ((adjmat[i].to_ulong() & mask) == mask) {
    mask ^= 1 << i;
    ++popcount;
    best = max(best, largest_clique(i)); // take i
    --popcount;
    mask ^= 1 << i;
  }
  return best;
}

signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int n, k; cin >> n >> k;
  vector<vector<int>> g(n);
  vector<int> degree(n);
  for (int i = 0; i < n; ++i) {
    cin >> degree[i];
    for (int j = 0; j < degree[i]; ++j) {
      int b; cin >> b;
      g[i].push_back(b);
    }
  }
  vector<bool> removed(n);
  priority_queue<pair<size_t, int>,
		 vector<pair<size_t, int>>,
		 greater<>> pq;
  for (int i = 0; i < n; ++i)
    pq.emplace(degree[i], i);
  for (auto& v : g)
    sort(v.begin(), v.end());
  
  auto has_edge = [&](int a, int b) { return binary_search(g[a].begin(), g[a].end(), b); };
  int best = 1;
  
  while (!pq.empty()) {
    auto [_, i] = pq.top();
    pq.pop();
    if (removed[i])
      continue;
    removed[i] = true;
    vector<int> nbs = g[i];
    nbs.erase(remove_if(nbs.begin(), nbs.end(), [&](int v){ return removed[v]; }), nbs.end());
    
    adjmat = {};
    mask = 0;
    popcount = 0;
    clique_n = nbs.size();
    for (size_t i = 0; i < nbs.size(); ++i) {
      for (size_t j = 0; j < nbs.size(); ++j) {
	if (i != j)
	  adjmat[i][j] = has_edge(nbs[i], nbs[j]);
      }
    }
    best = max(best, 1+largest_clique(0));   // 1+ because we always take i itself
    for (auto j : nbs) {
      --degree[j];
      pq.emplace(degree[j], j);
    }
  }
  cout << best << '\n';
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:50:10: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     auto [_, i] = pq.top();
          ^
politicaldevelopment.cpp:50:15: warning: unused variable '_' [-Wunused-variable]
     auto [_, i] = pq.top();
               ^

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