Submission #19523547


Source Code Expand

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

Submission Time
Task G - Mixture Drug
User t_tra
Language C++ (GCC 9.2.1)
Score 600
Code Size 2672 Byte
Status AC
Exec Time 361 ms
Memory 15904 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 7 ms 3568 KB
sample_02.txt AC 4 ms 3508 KB
sample_03.txt AC 4 ms 3420 KB
subtask_1_1.txt AC 2 ms 3408 KB
subtask_1_10.txt AC 332 ms 15752 KB
subtask_1_11.txt AC 3 ms 3464 KB
subtask_1_12.txt AC 335 ms 15724 KB
subtask_1_13.txt AC 275 ms 13628 KB
subtask_1_14.txt AC 352 ms 15804 KB
subtask_1_15.txt AC 2 ms 3388 KB
subtask_1_16.txt AC 340 ms 15756 KB
subtask_1_17.txt AC 328 ms 15840 KB
subtask_1_18.txt AC 332 ms 15852 KB
subtask_1_19.txt AC 4 ms 3436 KB
subtask_1_2.txt AC 361 ms 15904 KB
subtask_1_20.txt AC 339 ms 15752 KB
subtask_1_21.txt AC 329 ms 15736 KB
subtask_1_22.txt AC 330 ms 15696 KB
subtask_1_23.txt AC 2 ms 3452 KB
subtask_1_24.txt AC 28 ms 3960 KB
subtask_1_25.txt AC 331 ms 15668 KB
subtask_1_26.txt AC 329 ms 15820 KB
subtask_1_27.txt AC 329 ms 15808 KB
subtask_1_28.txt AC 330 ms 15740 KB
subtask_1_29.txt AC 330 ms 15664 KB
subtask_1_3.txt AC 67 ms 5780 KB
subtask_1_30.txt AC 2 ms 3580 KB
subtask_1_31.txt AC 2 ms 3520 KB
subtask_1_32.txt AC 7 ms 3560 KB
subtask_1_33.txt AC 23 ms 3916 KB
subtask_1_34.txt AC 341 ms 15752 KB
subtask_1_35.txt AC 330 ms 15812 KB
subtask_1_36.txt AC 332 ms 15808 KB
subtask_1_37.txt AC 325 ms 15728 KB
subtask_1_38.txt AC 328 ms 15692 KB
subtask_1_39.txt AC 328 ms 15820 KB
subtask_1_4.txt AC 330 ms 15668 KB
subtask_1_40.txt AC 332 ms 15724 KB
subtask_1_41.txt AC 328 ms 15844 KB
subtask_1_42.txt AC 331 ms 15812 KB
subtask_1_43.txt AC 332 ms 15852 KB
subtask_1_44.txt AC 340 ms 15820 KB
subtask_1_45.txt AC 338 ms 15748 KB
subtask_1_46.txt AC 350 ms 15776 KB
subtask_1_47.txt AC 333 ms 15736 KB
subtask_1_48.txt AC 339 ms 15668 KB
subtask_1_5.txt AC 85 ms 6224 KB
subtask_1_6.txt AC 334 ms 15836 KB
subtask_1_7.txt AC 130 ms 8360 KB
subtask_1_8.txt AC 335 ms 15736 KB
subtask_1_9.txt AC 171 ms 9564 KB