Submission #19053020


Source Code Expand

Copy
#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

Submission Time
Task G - Mixture Drug
User SSRS
Language C++ (GCC 9.2.1)
Score 600
Code Size 1372 Byte
Status AC
Exec Time 690 ms
Memory 11376 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 51
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 8 ms 3600 KB
sample_02.txt AC 3 ms 3380 KB
sample_03.txt AC 2 ms 3388 KB
subtask_1_1.txt AC 2 ms 3476 KB
subtask_1_10.txt AC 96 ms 11336 KB
subtask_1_11.txt AC 2 ms 3616 KB
subtask_1_12.txt AC 105 ms 11340 KB
subtask_1_13.txt AC 181 ms 9160 KB
subtask_1_14.txt AC 201 ms 11340 KB
subtask_1_15.txt AC 2 ms 3604 KB
subtask_1_16.txt AC 118 ms 11340 KB
subtask_1_17.txt AC 117 ms 11176 KB
subtask_1_18.txt AC 100 ms 11268 KB
subtask_1_19.txt AC 3 ms 3512 KB
subtask_1_2.txt AC 47 ms 11172 KB
subtask_1_20.txt AC 262 ms 11228 KB
subtask_1_21.txt AC 222 ms 11376 KB
subtask_1_22.txt AC 180 ms 11268 KB
subtask_1_23.txt AC 2 ms 3620 KB
subtask_1_24.txt AC 16 ms 3540 KB
subtask_1_25.txt AC 78 ms 11292 KB
subtask_1_26.txt AC 96 ms 11352 KB
subtask_1_27.txt AC 123 ms 11268 KB
subtask_1_28.txt AC 184 ms 11240 KB
subtask_1_29.txt AC 303 ms 11336 KB
subtask_1_3.txt AC 140 ms 4744 KB
subtask_1_30.txt AC 2 ms 3548 KB
subtask_1_31.txt AC 5 ms 3448 KB
subtask_1_32.txt AC 4 ms 3484 KB
subtask_1_33.txt AC 33 ms 3688 KB
subtask_1_34.txt AC 79 ms 11176 KB
subtask_1_35.txt AC 166 ms 11240 KB
subtask_1_36.txt AC 316 ms 11376 KB
subtask_1_37.txt AC 630 ms 11344 KB
subtask_1_38.txt AC 113 ms 11236 KB
subtask_1_39.txt AC 91 ms 11268 KB
subtask_1_4.txt AC 690 ms 11272 KB
subtask_1_40.txt AC 94 ms 11236 KB
subtask_1_41.txt AC 100 ms 11240 KB
subtask_1_42.txt AC 153 ms 11172 KB
subtask_1_43.txt AC 335 ms 11292 KB
subtask_1_44.txt AC 191 ms 11292 KB
subtask_1_45.txt AC 215 ms 11344 KB
subtask_1_46.txt AC 196 ms 11296 KB
subtask_1_47.txt AC 130 ms 11172 KB
subtask_1_48.txt AC 124 ms 11356 KB
subtask_1_5.txt AC 32 ms 5136 KB
subtask_1_6.txt AC 86 ms 11344 KB
subtask_1_7.txt AC 39 ms 6156 KB
subtask_1_8.txt AC 87 ms 11344 KB
subtask_1_9.txt AC 54 ms 7380 KB