oj.uz

Submission #691956

# Submission time Handle Problem Language Result Execution time Memory
691956 2023-02-01T03:30:41 Z beaboss Amusement Park (CEOI19_amusementpark) C++14
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll MOD = 998244353;

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

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

	vector<vector<ll> > adj2(n);

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

	}

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

			bool conn = false;
			for (auto val: adj2[ne]) if ((1<<val)&i)conn=true;
			// cout << (i^(1 << ne)) << dp[i].first << c << endl;
			if (!conn)continue;
			dp[i^(1 << ne)].second=((dp[i^(1 << ne)].second)%MOD+((dp[i].second)%MOD)+(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[]
	}
	ll ans = 1;
	vector<bool> v(n, false);
	for (int i = 0; i < n; i++) {

		if (!v[i]) {
			ll current=0;
			v[i] = true;
			queue<ll> q;
			q.push(i);
			while (!q.empty()) {
				ll cur = q.front();
				q.pop();
				current|=(1<<cur);
				for (auto val: adj2[cur]) if (!v[val]) {
					q.push(val);v[val]=true;
				}
			}
			ans = (ans * dp[current].second)%MOD;
		}
		
	}
	cout << ans << 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 212 KB Output is correct
3 Incorrect 0 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 212 KB Output is correct
3 Incorrect 0 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 212 KB Output is correct
3 Incorrect 0 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 212 KB Output is correct
3 Incorrect 0 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 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -