Submission #691946

#	Time	Username	Problem	Language	Result	Execution time	Memory
691946		beaboss	Amusement Park (CEOI19_amusementpark)	C++14	0 / 100	1 ms	212 KiB

amusementpark

#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;
			dp[i^(1 << ne)].second=((dp[i^(1 << ne)].second)%MOD+((dp[i].second)%MOD)+(dp[i].first*c)%MOD)%MOD;
			if (conn)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[]
	}
	cout << dp[(1<<n)-1].second << endl;

}

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