Submission #591657

#	Time	Username	Problem	Language	Result	Execution time	Memory
591657		Shin	Political Development (BOI17_politicaldevelopment)	C++14	0 / 100	4 ms	1768 KiB

politicaldevelopment

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

const int N = 5e4 + 7;
int n, k;
int deg[N];
bool vis[N];
bool dp[1 << 10];
bool has_edge[11][11];

vector<int> node;
vector<int> adj[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k;
  priority_queue<pair<int, int>> heap;
  for (int i = 1; i <= n; i ++) {
    cin >> deg[i];
    heap.emplace(- deg[i], i);
    for (int j = 0; j < deg[i]; j ++) {
      int u; cin >> u;
      adj[i].push_back(u);
    }
    sort(all(adj[i]));
  }

  auto calc = [&]() {
    int m = node.size();
    memset(has_edge, false, sizeof has_edge);
    for (int i = 0; i < m; i ++) {
      for (int j = 0; j < m; j ++) {
        has_edge[i][j] = binary_search(all(adj[node[i]]), node[j]);
      }
    }
    int res = 0;
    dp[0] = true;
    for (int mask = 1; mask < 1 << m; mask ++) {
      int f = -1;
      dp[mask] = true;
      for (int i = 0; i < m; i ++) {
        if (~(mask >> i) & 1) {
          continue;
        }
        if (f == -1) {
          f = i;
          dp[mask] = dp[mask ^ (1 << i)];
        } else {
          dp[mask] &= has_edge[f][i];
        }
      }
      if (dp[mask]) {
        maximize(res, __builtin_popcount(mask));
      }
    }
    return res;
  };

  int res = 0;
  for (int i = 0; i < n; i ++) {
    while (vis[heap.top().se]) {
      heap.pop();
    }
    int u = heap.top().se;
    heap.pop();
    vis[u] = true;
    node.clear();
    for (int v: adj[u]) if (!vis[v]) {
      deg[v] --;
      heap.emplace(-deg[v], v);
      node.push_back(v);
    }
    maximize(res, calc() + 1);
  }
  cout << res;
  return 0;
}

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