Submission #1247016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247016		julia_08	Political Development (BOI17_politicaldevelopment)	C++20	100 / 100	498 ms	24524 KiB

politicaldevelopment

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

const int MAXN = 5e4 + 10;

int deg[MAXN];

int marc[MAXN];

int dp[(1 << 11)];

set<int> adj[MAXN];

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int n, k; cin >> n >> k;

  for(int i=0; i<n; i++){

    int k; cin >> k;

    deg[i] = k;

    while(k--){
      int j; cin >> j;
      adj[i].insert(j);
    }

  }

  queue<int> q;

  for(int i=0; i<n; i++){
    if(deg[i] <= 10){
      marc[i] = 1;
      q.push(i);
    }
  }

  int ans = 1;

  while(!q.empty()){

    int v = q.front();
    q.pop();

    vector<int> vis;

    while(!adj[v].empty()){
      vis.push_back(*adj[v].begin());
      adj[v].erase(adj[v].begin());
    }

    int sz = vis.size();

    dp[0] = 1;

    for(int mask=1; mask<(1 << sz); mask++){
        
      int i = __lg(mask);

      int cnt = 1; // so o i

      for(int j=0; j<sz; j++){
        if(mask & (1 << j)){
          cnt += (adj[vis[i]].count(vis[j]));
        }
      }

      int sz_mask = __builtin_popcount(mask);

      dp[mask] = (dp[mask ^ (1 << i)] && (cnt == sz_mask));
      if(dp[mask]) ans = max(ans, sz_mask + 1);

    }

    for(auto u : vis){

      adj[u].erase(v);
      deg[u] --;

      if(deg[u] <= 10 && !marc[u]){
        marc[u] = 1;
        q.push(u);
      }

    }

  }

  int x = 0;

  for(int i=0; i<n; i++){
    if(!marc[i]){
      x ++;
    }
  }

  assert(x == 0);

  cout << ans << "\n";

  return 0;
}

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