Submission #696400

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

amusementpark

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

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:28:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   28 |  return printf("%d",(1ll*f[(1<<n)-1]*m%mod*inv2%mod+mod)%mod),0;
      |                 ~^  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                  |                                      |
      |                  int                                    long long int
      |                 %lld
amusementpark.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
amusementpark.cpp:17:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  for(int u,v,i=0;i<m;i++)scanf("%d%d",&u,&v),u--,v--,a[u][v]=a[v][u]=1;
      |                          ~~~~~^~~~~~~~~~~~~~

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