Submission #697239

#	Time	Username	Problem	Language	Result	Execution time	Memory
697239		vjudge1	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	1721 ms	4772 KiB

amusementpark

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1001000,mod=998244353;
int n,m,f[N],e[20][20],rc[N];
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1,x,y;i<=m;i++)
        scanf("%lld%lld",&x,&y),e[x-1][y-1]=e[y-1][x-1]=1;
    f[0]=1;
    for(int i=0;i<(1<<n);i++)
    {
        int sum=(i==0)?0:(__builtin_popcount(i));
        (sum%2==1)?(rc[i]=1):(rc[i]=-1);
        for(int j=0;j<n;j++)
            for(int k=j+1;k<n;k++)
                if(((i>>j)&1)&&((i>>k)&1)&&e[j][k])
                    rc[i]=0;
    }
    for(int i=1;i<(1<<n);i++)
        for(int j=i;j;j=((j-1)&i))
            f[i]=(f[i]+rc[j]*f[i^j]+mod)%mod;
    printf("%lld\n",f[(1<<n)-1]*m%mod*((mod+1)/2)%mod);
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
amusementpark.cpp:10:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         scanf("%lld%lld",&x,&y),e[x-1][y-1]=e[y-1][x-1]=1;
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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