oj.uz

Submission #1035290

# Submission time Handle Problem Language Result Execution time Memory
1035290 2024-07-26T08:52:35 Z vjudge1 Political Development (BOI17_politicaldevelopment) C++17
0 / 100
 34 ms 24948 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4;

mt19937 rng(time(nullptr) + 69);

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

bool solve(int tot, int x, int y) {
  if (curr.count() < tot || n-1 - y < x) 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();
  for (int i = 0; i < sz; i++) {
    prv = curr;
    curr &= bt[temp[i]];
    if (solve(tot, x-1, temp[i])) return 1;
    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[0][i].push_back(i);
    adj[1][i].push_back(i);
    for (int j = 0; j < x; j++) {
      int y; cin >> y;
      bt[i][y] = 1;
      cnt[y]++;
      adj[0][i].push_back(y);
      adj[1][y].push_back(i);
    }
  }

  int ans = 0;
  for (int i = 1; i <= k; i++) {
    for (int& j : rem) curr[j] = 1;
    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[0][rem[j]]) {
          if (cnt[k] >= i) c++; 
        }
        if (c >= i) {
          nw.push_back(rem[j]);
          continue;
        }
        ch = 1;
        for (int& k : adj[0][rem[j]]) {
          cnt[k]--;
        }
      }
      swap(nw, rem);
      if (!ch) break;
    }
  }

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

Compilation message

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2824 KB Output is correct
3 Incorrect 34 ms 24948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2824 KB Output is correct
3 Incorrect 34 ms 24948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23388 KB Output is correct
2 Incorrect 1 ms 3080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2824 KB Output is correct
3 Incorrect 34 ms 24948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2824 KB Output is correct
3 Incorrect 34 ms 24948 KB Output isn't correct
4 Halted 0 ms 0 KB -