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
Task G - Mixture Drug
User toku
Language C++ (GCC 9.2.1)
Score 600
Code Size 2275 Byte
Status
Exec Time 976 ms
Memory 15504 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
× 3
× 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 10 ms 3292 KB
sample_02.txt 2 ms 3340 KB
sample_03.txt 3 ms 3372 KB
subtask_1_1.txt 2 ms 3368 KB
subtask_1_10.txt 931 ms 15460 KB
subtask_1_11.txt 2 ms 3320 KB
subtask_1_12.txt 971 ms 15432 KB
subtask_1_13.txt 707 ms 13308 KB
subtask_1_14.txt 964 ms 15420 KB
subtask_1_15.txt 2 ms 3416 KB
subtask_1_16.txt 956 ms 15440 KB
subtask_1_17.txt 933 ms 15412 KB
subtask_1_18.txt 928 ms 15408 KB
subtask_1_19.txt 10 ms 3404 KB
subtask_1_2.txt 967 ms 15460 KB
subtask_1_20.txt 910 ms 15396 KB
subtask_1_21.txt 920 ms 15472 KB
subtask_1_22.txt 886 ms 15364 KB
subtask_1_23.txt 2 ms 3380 KB
subtask_1_24.txt 58 ms 3816 KB
subtask_1_25.txt 971 ms 15420 KB
subtask_1_26.txt 971 ms 15496 KB
subtask_1_27.txt 976 ms 15364 KB
subtask_1_28.txt 968 ms 15416 KB
subtask_1_29.txt 965 ms 15464 KB
subtask_1_3.txt 165 ms 5692 KB
subtask_1_30.txt 2 ms 3280 KB
subtask_1_31.txt 4 ms 3364 KB
subtask_1_32.txt 8 ms 3396 KB
subtask_1_33.txt 47 ms 3684 KB
subtask_1_34.txt 947 ms 15368 KB
subtask_1_35.txt 938 ms 15440 KB
subtask_1_36.txt 922 ms 15396 KB
subtask_1_37.txt 905 ms 15432 KB
subtask_1_38.txt 894 ms 15440 KB
subtask_1_39.txt 917 ms 15472 KB
subtask_1_4.txt 896 ms 15440 KB
subtask_1_40.txt 898 ms 15456 KB
subtask_1_41.txt 889 ms 15420 KB
subtask_1_42.txt 886 ms 15428 KB
subtask_1_43.txt 929 ms 15340 KB
subtask_1_44.txt 908 ms 15428 KB
subtask_1_45.txt 912 ms 15500 KB
subtask_1_46.txt 971 ms 15504 KB
subtask_1_47.txt 912 ms 15432 KB
subtask_1_48.txt 939 ms 15412 KB
subtask_1_5.txt 218 ms 6124 KB
subtask_1_6.txt 948 ms 15432 KB
subtask_1_7.txt 356 ms 8036 KB
subtask_1_8.txt 931 ms 15412 KB
subtask_1_9.txt 441 ms 9124 KB