oj.uz

Submission #691941

# Submission time Handle Problem Language Result Execution time Memory
691941 2023-02-01T02:59:43 Z beaboss Amusement Park (CEOI19_amusementpark) C++14
0 / 100
 1 ms 300 KB 
#include <bits/stdc++.h>

using namespace std;


int MOD = 998244353;

int main() {
	int n, m;
	cin >> n >> m;

	vector<vector<int> > adj(n);

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;b--;
		adj[a].push_back(b);
	}

	vector<pair<int, int> > dp(1<<n, {0, 0});
	dp[0]={1, 0};
	for (int i = 0; i < n; i++) dp[(1 << i)] = {1, 0};
	for (int i = 1; i < (1<<n); i++) {
		// cout << i << dp[i].first << dp[i].second << endl;
		for (int ne = 0; ne < n; ne++) {
			if ((1 << ne) & i) continue;
			int c = 0;
			for (auto val: adj[ne]) {
				if ((1 << val) & i) {
					c++;
				}
			}

			dp[i^(1 << ne)].second=((dp[i^(1 << ne)].second)%MOD+(dp[i].second+dp[i].first*c)%MOD)%MOD;
			dp[i^(1 << ne)].first=(dp[i^(1 << ne)].first+dp[i].first)%MOD;
			// cout << i<<(ne) << dp[i^(1 << ne)].second << endl;
		}
	}
	cout << dp[(1<<n)-1].second << endl;

}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 37.0

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