Submission #19053020

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, M;
  cin >> N >> M;
  vector<int> a(M), b(M);
  for (int i = 0; i < M; i++){
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
  }
  int X = N / 2;
  int Y = N - X;
  vector<int> A(1 << X);
  for (int i = 0; i < (1 << X); i++){
    A[i] = __builtin_popcount(i);
    for (int j = 0; j < M; j++){
      if (b[j] < X){
        if ((i >> a[j] & 1) && (i >> b[j] & 1)){
          A[i] = 0;
          break;
        }
      }
    }
  }
  vector<int> B(1 << Y);
  for (int i = 0; i < (1 << Y); i++){
    B[i] = __builtin_popcount(i);
    for (int j = 0; j < M; j++){
      if (a[j] >= X){
        if ((i >> (a[j] - X) & 1) && (i >> (b[j] - X) & 1)){
          B[i] = 0;
          break;
        }
      }
    }
  }
  for (int i = 0; i < X; i++){
    for (int j = 0; j < (1 << X); j++){
      if (j >> i & 1){
        A[j] = max(A[j], A[j - (1 << i)]);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < (1 << Y); i++){
    if (B[i] > 0){
      int t = (1 << X) - 1;
      for (int j = 0; j < M; j++){
        if (a[j] < X && b[j] >= X){
          if (i >> (b[j] - X) & 1){
            if (t >> a[j] & 1){
              t -= 1 << a[j];
            }
          }
        }
      }
      ans = max(ans, A[t] + B[i]);
    }
  }
  cout << ans << endl;
}

Submission Info

Judge Result