Submission #741217

#	Time	Username	Problem	Language	Result	Execution time	Memory
741217		nishkarsh	Amusement Park (CEOI19_amusementpark)	C++14	7 / 100	1 ms	312 KiB

amusementpark

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 18;
const int mod = 998244353;
ll ways[1<<N][N];
ll sum[1<<N][N];
int undirected_edge[N];
int rev_directed_edge[N];
int main(){
	int n,m,a,b;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> a >> b;
		a--;b--;
		rev_directed_edge[b] ^= (1<<a);
		undirected_edge[a] ^= (1<<b);
		undirected_edge[b] ^= (1<<a);
	}
	for(int i = 0; i < n; i++) ways[1<<i][i] = 1;
	for(int i = 0; i < (1<<n); i++){
		if(! (i&(i-1))) continue;
		for(int j = 0; j < n; j++){
			if(! (i&(1<<j))) continue;
			for(int k = 0; k < n; k++){
				if((! (i&(1<<j))) || (k == j)) continue;
				if((undirected_edge[j]&(1<<k)) || (k > j)){
					ways[i][j] += ways[i^(1<<j)][k];
					sum[i][j] += sum[i^(1<<j)][k];
				}
			}
			ways[i][j] %= mod;
			sum[i][j] += ways[i][j] * __builtin_popcount(rev_directed_edge[j]&i);
			sum[i][j] %= mod;
		}
	}
	ll ans = 0;
	for(int i = 0; i < n; i++) ans += sum[(1<<n)-1][i];
	ans %= mod;
	cout << ans;
	return 0;
}

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