Submission #742060

#	Time	Username	Problem	Language	Result	Execution time	Memory
742060		nishkarsh	Amusement Park (CEOI19_amusementpark)	C++14	100 / 100	699 ms	3784 KiB

amusementpark

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 18;
const int mod = 998244353;
bool isindep[1<<N];
ll dp[1<<N];
int popcnt[1<<N];
int undirected_edge[N];
int main(){
	int n,m,a,b;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> a >> b;
		a--;b--;
		undirected_edge[a] ^= (1<<b);
		undirected_edge[b] ^= (1<<a);
	}
	for(int i = 0; i < (1<<n); i++){
		int edges = 0;
		for(int j = 0; j < n; j++){
			if(i&(1<<j)){
				popcnt[i]++;
				edges |= undirected_edge[j];
			}
		}
		if((edges&i) == 0) isindep[i] = true;
	}
	dp[0] = 1;
	for(int i = 1; i < (1<<n); i++){
		for(int j = i; j > 0; j = (j-1)&i){
			if(isindep[j]){
				if(popcnt[j]&1) dp[i] += dp[i^j];
				else dp[i] -= dp[i^j];
			}
		}
		dp[i]%=mod;
      	if(dp[i] < 0) dp[i] += mod;
	}
	ll ans = dp[(1<<n)-1];
	if(ans&1) ans += mod;
	ans >>= 1;
	ans *= m; ans %= mod;
	cout << ans;
	return 0;
}

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