Contest Duration: ~ (local time) (180 minutes)

Submission #17416883

Source Code Expand

Copy
```#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0; i<ll(n); i++)
#define FOR(i,m,n) for(ll i=ll(m); i<ll(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VP vector<pair<ll,ll>>
#define VPP vector<pair<int,pair<int,int>>>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)
typedef pair <int, int> P;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }

const int  INF = (1 << 30) - 1;
const ll INFL = 1LL << 60;
const ll mod = 1000000007;

bool b[41][41];

int main() {

int n, m;
cin >> n >> m;

REP(i, m) {
int a, c;
cin >> a >> c;
a--; c--;
b[a][c] = true;
b[c][a] = true;
}

int nn = n / 2;
n -= nn;

VI dp((1 << n), 0);
VI dq((1 << n), (1 << nn) - 1);
FOR(i, 1, (1 << n)) {
VI  a;
REP(j, n) {
if (i&(1 << j)) {
a.push_back(j);
}
}
int mm = a.size();
int ma = 0;
REP(j, mm) {
ll p = 0;
bool check = true;
REP(k, mm) {
if (j == k)continue;
p += (1 << a[k]);
if (b[a[j]][a[k]])check = false;
}
chmax(ma, dp[p] + (check ? 1 : 0));
}
dp[i] = ma;
ll p = 0;
for (int j : a) {
FOR(k, n, nn + n) {
if (b[j][k]) {
p |= (1 << (k - n));
}
}
}
dq[i] ^= p;
}
VI dr((1 << nn), 0);
FOR(i, 1, (1 << nn)){
VI  a;
REP(j, n) {
if (i&(1 << j)) {
a.push_back(j + n);
}
}
int mm = a.size();
int ma = 0;
REP(j, mm) {
ll p = 0;
bool check = true;
REP(k, mm) {
if (j == k)continue;
p += (1 << (a[k] - n));
if (b[a[j]][a[k]])check = false;
}
chmax(ma, dr[p] + (check ? 1 : 0));
}
dr[i] = ma;
}

int ans = 0;

REP(i, (1 << n)) {
chmax(ans, dp[i] + dr[dq[i]]);
}
cout << ans << endl;

}```

#### Submission Info

Submission Time 2020-10-16 12:50:07+0900 G - Mixture Drug toku C++ (GCC 9.2.1) 600 2275 Byte AC 976 ms 15504 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
Case Name Status Exec Time Memory
sample_01.txt 10 ms 3292 KB
sample_02.txt 2 ms 3340 KB
sample_03.txt 3 ms 3372 KB