Submission #698981

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

amusementpark

#include <bits/stdc++.h>
using namespace std;
const int maxn=20,maxm=262200;
const int md=998244353,i2=499122177;
int n,m,i,j,u,v,b,f[maxm],g[maxm];
bool e[maxn][maxn];
int main(){
	scanf("%d%d",&n,&m); b=1<<n;
	for(i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		--u; --v; e[u][v]=e[v][u]=1;
	}
	memset(g,-1,sizeof(g));
	for(i=1;i<b;i<<=1) g[i]=0; f[0]=1;
	for(i=1;i<b;++i){
		if(g[i]){
			if(~g[v=i^(1<<(u=__lg(i&-i)))])
				for(;v;v^=j) if(e[u][__lg(j=v&-v)]) break;
			if(!v) g[i]=!g[i^(1<<u)];
		}
		for(j=i,v=0;j;j=(j-1)&i){
			if(~g[j]){
				u=f[i^j]; if(g[j]) u=md-u;
				v-=((v+=u)>=md)*md;
			}
		}
		f[i]=v;
	}
	printf("%d",1LL*f[b-1]*m%md*i2%md);
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:14:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   14 |  for(i=1;i<b;i<<=1) g[i]=0; f[0]=1;
      |  ^~~
amusementpark.cpp:14:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   14 |  for(i=1;i<b;i<<=1) g[i]=0; f[0]=1;
      |                             ^
amusementpark.cpp:29:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   29 |  printf("%d",1LL*f[b-1]*m%md*i2%md);
      |          ~^  ~~~~~~~~~~~~~~~~~~~~~
      |           |                    |
      |           int                  long long int
      |          %lld
amusementpark.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |  scanf("%d%d",&n,&m); b=1<<n;
      |  ~~~~~^~~~~~~~~~~~~~
amusementpark.cpp:10:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |   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