Submission #697267

#	Time	Username	Problem	Language	Result	Execution time	Memory
697267		vjudge1	Amusement Park (CEOI19_amusementpark)	C++14	100 / 100	2572 ms	2572 KiB

amusementpark

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=18,mod=998244353,inv=(mod+1)/2;
int n,m,u,v,f[1<<N],c[1<<N],ans;
bool a[N][N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		a[u-1][v-1]=a[v-1][u-1]=1;
	}
	for(int i=0;i<(1<<n);i++)
	{
		c[i]=-1;
		for(int j=0;j<n;j++)
		{
			if((i>>j)&1) 
			{
				c[i]=-c[i];
				for(int k=j+1;k<n;k++)
					if(((i>>k)&1)&&a[j][k]) c[i]=0;
			}
			if(!c[i]) break;
		}
	}
	f[0]=1;
	for(int i=1;i<(1<<n);i++)
		for(int j=i;j;j=(j-1)&i)
			if(c[j]) f[i]=((ll)f[i]+f[i-j]*c[j]+mod)%mod;
	ans=(ll)f[(1<<n)-1]*m%mod*inv%mod;
	printf("%d",ans);
	return 0;
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
amusementpark.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~

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