Submission #1035318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035318		vjudge1	Political Development (BOI17_politicaldevelopment)	C++17	4 / 100	2457 ms	524288 KiB

politicaldevelopment

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4, X = 3e6;

mt19937 rng(time(nullptr) + 69);

int n, k, counter, cnt[N];
vector<int> rem, adj[N];
bitset<N> bt2[N], bt[N], curr;

bool solve(int tot, int x, int y) {
  //cerr << tot << " " << x << " " << y << " " << curr.count() << endl;
  if (curr.count() < tot) return 0;
  else if (!x) return 1;

  // tengo que pillar x mas, mayores que y, tengo curr odiados

  vector<int> temp;
  int sz = rem.size();
  for (int i = sz-1; i >= 0; i--) {
    if (rem[i] <= y) break;
    temp.push_back(rem[i]);
  }
  shuffle(temp.begin(), temp.end(), rng);

  sz = temp.size();
  if (sz < x-1) return 0;
  for (int i = 0; i < sz; i++) {
    bitset<N> prv = curr;
    curr &= bt[temp[i]];
    if (solve(tot, x-1, temp[i])) return 1;
    if (counter++ >= X) return 0;
    swap(curr, prv);
  }
  return 0;
}

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

  cin >> n >> k;
  memset(cnt, 0, sizeof(cnt));
  rem.resize(n);
  for (int i = 0; i < n; i++) {
    rem[i] = i;
    int x; cin >> x;

    bt[i][i] = 1;
    cnt[i]++;
    adj[i].push_back(i);

    for (int j = 0; j < x; j++) {
      int y; cin >> y;
      bt2[i][y] = 1;

      if (bt2[y][i]) {
        bt[i][y] = 1;
        cnt[y]++;
        adj[i].push_back(y);

        bt[y][i] = 1;
        cnt[i]++;
        adj[y].push_back(i);
      }
    }
  }

  int ans = 0;
  for (int i = 1; i <= k; i++) {
    curr.reset();
    for (int& j : rem) curr[j] = 1;
    counter = 0;
    if (!solve(i, i, -1)) break;
    ans = i;

    // limpiar
    while (1) {
      int sz = rem.size();
      vector<int> nw;
      bool ch = 0;
      for (int j = 0; j < sz; j++) {
        int c = 0;
        for (int& k : adj[rem[j]]) {
          if (cnt[k] >= i) c++; 
        }
        if (c >= i) {
          nw.push_back(rem[j]);
          continue;
        }
        ch = 1;
        for (int& k : adj[rem[j]]) {
          cnt[k]--;
        }
      }
      swap(nw, rem);
      if (!ch) break;
    }
  }

  cout << ans << "\n";
}

/*
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4, X = 1e6;

mt19937 rng(time(nullptr) + 69);

int n, k, counter, cnt[N];
vector<int> rem, adj[N];
bitset<N> bt[N], curr;

bool solve(int tot, int x, int y) {
  //cerr << tot << " " << x << " " << y << " " << curr.count() << endl;
  if (curr.count() < tot) return 0;
  else if (!x) return 1;

  // tengo que pillar x mas, mayores que y, tengo curr odiados

  vector<int> temp;
  int sz = rem.size();
  for (int i = sz-1; i >= 0; i--) {
    if (rem[i] <= y) break;
    temp.push_back(rem[i]);
  }
  shuffle(temp.begin(), temp.end(), rng);

  sz = temp.size();
  if (sz < x-1) return 0;
  for (int i = 0; i < sz; i++) {
    bitset<N> prv = curr;
    curr &= bt[temp[i]];
    if (solve(tot, x-1, temp[i])) return 1;
    if (counter++ >= X) return 0;
    swap(curr, prv);
  }
  return 0;
}

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

  cin >> n >> k;
  memset(cnt, 0, sizeof(cnt));
  rem.resize(n);
  for (int i = 0; i < n; i++) {
    rem[i] = i;
    int x; cin >> x;
    bt[i][i] = 1;
    cnt[i]++;
    adj[i].push_back(i);
    for (int j = 0; j < x; j++) {
      int y; cin >> y;
      bt[i][y] = 1;
      cnt[y]++;
      adj[i].push_back(y);
    }
  }

  if (k == 1) {
    cout << "1\n";
  }
  else if (k == 2) {
    int ans = 0;
    for (int i = 1; i <= k; i++) {
      curr.reset();
      for (int& j : rem) curr[j] = 1;
      counter = 0;
      if (!solve(i, i, -1)) break;
      ans = i;

      // limpiar
      while (1) {
        int sz = rem.size();
        vector<int> nw;
        bool ch = 0;
        for (int j = 0; j < sz; j++) {
          int c = 0;
          for (int& k : adj[rem[j]]) {
            if (cnt[k] >= i) c++; 
          }
          if (c >= i) {
            nw.push_back(rem[j]);
            continue;
          }
          ch = 1;
          for (int& k : adj[rem[j]]) {
            cnt[k]--;
          }
        }
        swap(nw, rem);
        if (!ch) break;
      }
    }
    cout << ans << "\n";
  }
  else if (k == 3) {
    int ans = 1;
    for (int i = 0; i < n; i++) {
      for (int& j : adj[i]) {

      }
    }
  }
  else {

  }
}
*/

Compilation message (stderr)

politicaldevelopment.cpp: In function 'bool solve(int, int, int)':
politicaldevelopment.cpp:16:20: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |   if (curr.count() < tot) return 0;
      |       ~~~~~~~~~~~~~^~~~~

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