Submission #19523547

---

Source Code Expand

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;

int main()
{
	int N, M;
	cin >> N >> M;
	vvi G(N);
	for (auto i = 0; i < M; ++i)
	{
		int a, b;
		cin >> a >> b;
		--a;
		--b;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	auto half = N / 2;
	auto calc = [&](int s, int e, vector<bool>& out)
	{
		for (auto i = s; i < e; ++i)
		{
			for (auto j : G[i])
			{
				if (j >= s && j < e)
				{
					auto bit = (1 << (i - s)) | (1 << (j - s));
					out[bit] = false;
				}
			}
		}

		auto num = e - s;
		for (auto i = 0; i < 1 << num; ++i)
		{
			for (auto j = 0; j < num; ++j)
			{
				auto bit = 1 << j;
				if ((i & bit) == 0)
				{
					out[i | bit] = out[i | bit] && out[i];
				}
			}
		}
	};

	auto numR = (N - half);
	vector<bool> leftInd(1 << half, true);
	vector<bool> rightInd(1 << numR, true);
	calc(0, half, leftInd);
	calc(half, N, rightInd);

	vi l2r(1 << half, (1 << numR) - 1);
	for (auto i = 0; i < half; ++i)
	{
		for (auto j : G[i])
		{
			if (j < half)
			{
				continue;
			}
			auto lbit = 1 << i;
			auto rbit = 1 << (j - half);
			l2r[lbit] = l2r[lbit] & ~rbit;
		}
	}

	for (auto i = 0; i < 1 << half; ++i)
	{
		for (auto j = 0; j < half; ++j)
		{
			auto bit = 1 << j;
			if ((i & bit) == 0)
			{
				l2r[i | bit] = l2r[i | bit] & l2r[i];
			}
		}
	}

	vi sumRight(1 << numR, 0);
	for (auto i = 0; i < 1 << numR; ++i)
	{
		if (rightInd[i])
		{
			auto sum = 0;
			for (auto j = 0; j < numR; ++j)
			{
				if ((i & (1 << j)) != 0)
				{
					++sum;
				}
			}

			sumRight[i] = sum;
		}
	}

	vi val(1 << numR, 0);
	for (auto i = 0; i < 1 << numR; ++i)
	{
		for (auto j = 0; j < numR; ++j)
		{
			auto bit = 1 << j;
			if ((i & bit) == 0)
			{
				val[i | bit] = max(val[i | bit], max(val[i], sumRight[i | bit]));
			}
		}
	}
	
	auto ans = 0;
	for (auto i = 0; i < 1 << half; ++i)
	{
		if (leftInd[i])
		{
			auto sum = 0;
			for (auto j = 0; j < numR; ++j)
			{
				if ((i & (1 << j)) != 0)
				{
					++sum;
				}
			}

			ans = max(ans, val[l2r[i]] + sum);
		}
	}

	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result