Submission #807383

#	Time	Username	Problem	Language	Result	Execution time	Memory
807383		tch1cherin	Political Development (BOI17_politicaldevelopment)	C++17	39 / 100	379 ms	64044 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;

const int MAX_N_SMALL = 5005;
const int MAX_N_BIG = 50005;
bool adj[MAX_N_SMALL][MAX_N_SMALL] = {};

struct SmallKSolution {
  int solve(int N, int K, vector<vector<int>> G) {
    if (K == 1) {
      return 1;
    }
    bool good = false;
    for (int i = 0; i < N; i++) {
      good |= !G[i].empty();
    }
    if (K == 2) {
      return 1 + (int)good;
    }
    for (int i = 0; i < N; i++) {
      for (int j : G[i]) {
        adj[i][j] = true;
      }
    }
    for (int i = 0; i < N; i++)
      for (int j : G[i])
        for (int k : G[j])
          if (adj[i][k])
            return 3;
    
    return 1 + (int)good;
  }
};

struct SmallMaxDegreeSolution {
  int solve(int N, int K, vector<vector<int>> G) {
    vector<int> pos(N, -1);
    int ans = 0;
    for (int i = 0; i < N; i++) {
      int D = (int)G[i].size();
      for (int j = 0; j < D; j++) {
        pos[G[i][j]] = j + 1;
      }
      pos[i] = 0;
      vector<int> mask(D + 1);
      mask[0] = (1 << (D + 1)) - 1;
      for (int j : G[i]) {
        mask[pos[j]] |= 1 << pos[j];
        for (int k : G[j]) {
          if (pos[k] != -1) {
            mask[pos[j]] |= 1 << pos[k];
          }
        }
      }
      for (int clique = 0; clique < (1 << D); clique++) {
        int msk = mask[0];
        for (int j = 0; j < D; j++) {
          if ((clique >> j) & 1) {
            msk &= mask[j + 1];
          }
        }
        if ((clique & msk) == clique) {
          ans = max(ans, __builtin_popcount(clique) + 1);
        }
      } 
      pos[i] = -1;
      for (int j = 0; j < D; j++) {
        pos[G[i][j]] = -1;
      }
    }
    return ans;
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, K;
  cin >> N >> K;
  vector<vector<int>> G(N);
  for (int i = 0; i < N; i++) {
    int D;
    cin >> D;
    G[i].resize(D);
    for (int j = 0; j < D; j++) {
      cin >> G[i][j];
    }
  }
  int max_degree = 0;
  for (int i = 0; i < N; i++) {
    max_degree = max(max_degree, (int)G[i].size());
  }
  if (max_degree > 10) {
    cout << SmallKSolution().solve(N, K, G) << "\n";
  } else {
    cout << SmallMaxDegreeSolution().solve(N, K, G) << "\n";
  }
}

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