oj.uz

Submission #1111029

# Submission time Handle Problem Language Result Execution time Memory
1111029 2024-11-11T10:20:07 Z NDT134 Amusement Park (CEOI19_amusementpark) C++14
0 / 100
 1 ms 336 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -