Submission #1086411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086411		hahahaha	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	1000 ms	309332 KiB

politicaldevelopment

#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';
}

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