Submission #1111029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111029		NDT134	Amusement Park (CEOI19_amusementpark)	C++14	0 / 100	1 ms	336 KiB

amusementpark

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
using pi = pair<int, int>;
int mod = 998244353;
int main() {
	int n, m; cin >> n >> m;
	vector<vector<int>> g(n), s(n, vector<int>(n));
	for (int i = 0; i < m; i++)
	{
		int a, b; cin >> a >> b; a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
		s[a][b] = 1; s[b][a] = 1;
	}
	int p = 1;
	for (int i = 0; i < n; i++)
	{
		p *= 2;
	}
	vector<long long> dp(p); vector<int> n2(p), n1(p);
	vector<vector<int>> b(p, vector<int> (n)), v1(p), v2(p);

	for (int i = 0; i < p; i++)
	{
		int x = i;
		for (int k = 0; k < n; k++)
		{
			b[i][k] = x % 2;
			x /= 2;
		}
	}
	
	for (int i = 0; i < p; i++)
	{
		for (int j = 0; j < i; j++)
		{
			bool bb = 1;
			for (int k = 0; k < n; k++)
			{
				if (b[i][k] < b[j][k])
				{
					bb = 0;
				}
			}
			if (bb)
			{
				v1[i].push_back(j); n2[i]++; n1[i]++;
				v2[j].push_back(i); 
			}
		}
	}

	dp[0] = 1;
	queue<int> q; q.push(0);
	while (!q.empty())
	{
		int x = q.front(); q.pop();
		for (int y : v1[x])
		{
			vector<int> a;
			for (int i = 0; i < n; i++)
			{
				if (b[y][i])
				{
					a.push_back(i);
				}
			}
			int k = a.size();
			bool bb = 1;
			for (int i = 0; i < k; i++)
			{
				for (int j = 0; j < i; j++)
				{
					if (s[i][j])
					{
						bb = 0;
					}
				}
			}
			dp[x] += bb * (2 * (k % 2) - 1) * dp[x - y];
			dp[x] %= mod;
		}
		for (int y : v2[x])
		{
			n2[y]--;
			if (!n2[y])
			{
				q.push(y);
			}
		}
		if (n1[x] == 1)
		{
			dp[x] = 1;
		}
	}

	std::cout << (dp[p - 1] * m / 2) % mod << endl;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37