Submission #223815

#	Time	Username	Problem	Language	Result	Execution time	Memory
223815		jk_	Political Development (BOI17_politicaldevelopment)	C++14	23 / 100	250 ms	524292 KiB

politicaldevelopment

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

int clique_n;
array<bitset<10>, 10> adjmat;
vector<uint8_t> selected;
int largest_clique(int i) {
  if (i == clique_n)
    return selected.size();
  int best = largest_clique(i+1);  // skip i

  bool can_take_i = true;
  for (auto j : selected) {
    if (!adjmat[i][j]) {
      can_take_i = false;
      break;
    }
  }
  if (can_take_i) {
    selected.push_back(i);
    best = max(best, largest_clique(i)); // take i
    selected.pop_back();
  }
  return best;
}

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

  int n, m; cin >> n >> m;
  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>> 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;
    vector<int> nbs = g[i];
    nbs.erase(remove_if(nbs.begin(), nbs.end(), [&](int v){ return removed[v]; }),
	      nbs.end());
    
    adjmat = {};
    selected.clear();
    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
    removed[i] = true;
    for (auto i : nbs) {
      --degree[i];
      pq.emplace(degree[i], i);
    }
  }
  cout << best << '\n';
}

Compilation message (stderr)

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

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