Submission #391315

#TimeUsernameProblemLanguageResultExecution timeMemory
391315HegdahlPolitical Development (BOI17_politicaldevelopment)C++17
100 / 100
925 ms309108 KiB
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,sse,sse2")
#include <bits/stdc++.h>
 
using namespace std;
 
const int mxN = 50000;
using S = bitset<mxN>;
 
S g[mxN];
 
int ans = 0;

void find_max(S can, int has) {
  ans = max(has, ans);

  while (can.any()) {
    int cur = (int)can._Find_first();
    can.reset(cur);

    S nxt_s = can & g[cur];
    if ((int)nxt_s.count()+has+1 > ans) {
      find_max(nxt_s, has+1);
    }
  }
}
 
int main() {
  ios::sync_with_stdio(0);cin.tie(0);
 
  int n, k; cin >> n >> k;
 
  for (int i = 0; i < n; ++i) {
    int s; cin >> s;
    g[i].set(i);
    for (int ss = 0; ss < s; ++ss) {
      int j; cin >> j;
      g[i].set(j);
    }
  }
 
  /*
  for (int i = 0; i < n; ++i)
    cerr << g[i] << '\n'; // */
 
  S init;
  for (int i = 0; i < n; ++i) init.set(i);
  find_max(init, 0);
 
  cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...