oj.uz

Submission #591657

# Submission time Handle Problem Language Result Execution time Memory
591657 2022-07-07T17:54:32 Z Shin Political Development (BOI17_politicaldevelopment) C++14
0 / 100
 4 ms 1768 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

const int N = 5e4 + 7;
int n, k;
int deg[N];
bool vis[N];
bool dp[1 << 10];
bool has_edge[11][11];

vector<int> node;
vector<int> adj[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k;
  priority_queue<pair<int, int>> heap;
  for (int i = 1; i <= n; i ++) {
    cin >> deg[i];
    heap.emplace(- deg[i], i);
    for (int j = 0; j < deg[i]; j ++) {
      int u; cin >> u;
      adj[i].push_back(u);
    }
    sort(all(adj[i]));
  }

  auto calc = [&]() {
    int m = node.size();
    memset(has_edge, false, sizeof has_edge);
    for (int i = 0; i < m; i ++) {
      for (int j = 0; j < m; j ++) {
        has_edge[i][j] = binary_search(all(adj[node[i]]), node[j]);
      }
    }
    int res = 0;
    dp[0] = true;
    for (int mask = 1; mask < 1 << m; mask ++) {
      int f = -1;
      dp[mask] = true;
      for (int i = 0; i < m; i ++) {
        if (~(mask >> i) & 1) {
          continue;
        }
        if (f == -1) {
          f = i;
          dp[mask] = dp[mask ^ (1 << i)];
        } else {
          dp[mask] &= has_edge[f][i];
        }
      }
      if (dp[mask]) {
        maximize(res, __builtin_popcount(mask));
      }
    }
    return res;
  };

  int res = 0;
  for (int i = 0; i < n; i ++) {
    while (vis[heap.top().se]) {
      heap.pop();
    }
    int u = heap.top().se;
    heap.pop();
    vis[u] = true;
    node.clear();
    for (int v: adj[u]) if (!vis[v]) {
      deg[v] --;
      heap.emplace(-deg[v], v);
      node.push_back(v);
    }
    maximize(res, calc() + 1);
  }
  cout << res;
  return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 4 ms 1748 KB Output is correct
4 Correct 3 ms 1712 KB Output is correct
5 Correct 3 ms 1768 KB Output is correct
6 Correct 3 ms 1748 KB Output is correct
7 Correct 3 ms 1748 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Incorrect 2 ms 1644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 4 ms 1748 KB Output is correct
4 Correct 3 ms 1712 KB Output is correct
5 Correct 3 ms 1768 KB Output is correct
6 Correct 3 ms 1748 KB Output is correct
7 Correct 3 ms 1748 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Incorrect 2 ms 1644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 4 ms 1748 KB Output is correct
4 Correct 3 ms 1712 KB Output is correct
5 Correct 3 ms 1768 KB Output is correct
6 Correct 3 ms 1748 KB Output is correct
7 Correct 3 ms 1748 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Incorrect 2 ms 1644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 4 ms 1748 KB Output is correct
4 Correct 3 ms 1712 KB Output is correct
5 Correct 3 ms 1768 KB Output is correct
6 Correct 3 ms 1748 KB Output is correct
7 Correct 3 ms 1748 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Incorrect 2 ms 1644 KB Output isn't correct
11 Halted 0 ms 0 KB -