Submission #696744

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

amusementpark

#include<bits/stdc++.h>
#define ll long long
#define lll __int128
#define db double
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
using namespace std;
namespace IO
{
	const int SZ=1<<20;
	char gchar()
	{
	    static char buf[SZ];
	    static int i=SZ;
	    if(i==SZ)i=0,fread(buf,1,SZ,stdin);
	    return buf[i++];
	}
	void pchar(char c)
	{
	    static char buf[SZ];
	    static int i=0;
	    if(c)buf[i++]=c;
	    if(!c||i==SZ)fwrite(buf,1,i,stdout),i=0;
	}
	void pstr(string s,char end='\n')
	{
		for(char c:s)pchar(c);
		pchar(end);
	}
	template<typename T>void read(T &x)
	{
	    x=0;int f=1;
	    static char c;
	    while((c=gchar())>'9'||c<'0')if(c=='-')f=-1;
	    x=c-'0';
	    while((c=gchar())>='0'&&c<='9')
			x=(x<<1)+(x<<3)+(c^48);
		x*=f;
	}
	template<typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);}
	template<typename T>void i_write(T x)
	{
	    if(x>9)i_write(x/10);
	    pchar(x%10+'0');
	}
	template<typename T>void write(T x,char end='\n')
	{
	    if(x<0)pchar('-'),x=-x;
	    if(x>9)i_write(x/10);
	    pchar(x%10+'0');
	    pchar(end);
	}
}
using IO::read;
using IO::write;
const int N=400,mod=998244353,inv2=(mod+1)>>1;
int n,m,x[N],y[N],f[1<<18];
bool flg[1<<18];
int main()
{
	read(n,m);
	for(int i=1;i<=m;i++)read(x[i],y[i]);
	for(int msk=0;msk<(1<<n);msk++)
		for(int i=1;i<=m;i++)
			if((msk&(1<<x[i]-1))&&(msk&(1<<y[i]-1)))flg[msk]=1;
	f[0]=1;
	for(int msk=1;msk<(1<<n);msk++)
		for(int s=msk;s;s=msk&(s-1))
			if(!flg[s])f[msk]=(0ll+f[msk]+(__builtin_popcount(s)&1?1:-1)*f[msk^s]+mod)%mod;
	printf("%lld",1ll*m*inv2%mod*f[(1<<n)-1]%mod);
	IO::pchar(0);
	return 0;
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:68:20: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   68 |    if((msk&(1<<x[i]-1))&&(msk&(1<<y[i]-1)))flg[msk]=1;
      |                ~~~~^~
amusementpark.cpp:68:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   68 |    if((msk&(1<<x[i]-1))&&(msk&(1<<y[i]-1)))flg[msk]=1;
      |                                   ~~~~^~
amusementpark.cpp: In function 'char IO::gchar()':
amusementpark.cpp:18:24: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |      if(i==SZ)i=0,fread(buf,1,SZ,stdin);
      |                   ~~~~~^~~~~~~~~~~~~~~~

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