Submission #583533

#	Time	Username	Problem	Language	Result	Execution time	Memory
583533		urd05	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	1890 ms	3568 KiB

amusementpark

#include <bits/stdc++.h>
using namespace std;

int n,m;
bool arr[18][18];
const int mod=998244353;
long long dp[262144];
int p[262144];

int main() {
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        u--;
        v--;
        arr[u][v]=true;
    }
    memset(p,-1,sizeof(p));
    for(int i=0;i<(1<<n);i++) {
        int cnt=0;
        for(int j=0;j<n;j++) {
            if (i&(1<<j)) {
                cnt++;
            }
        }
        for(int j=0;j<n;j++) {
            for(int k=0;k<n;k++) {
                if (i&(1<<j)) {
                    if (i&(1<<k)) {
                        if (arr[j][k]||arr[k][j]) {
                            p[i]=0;
                            break;
                        }
                    }
                }
            }
        }
        if (cnt%2==1) {
            p[i]=(mod-p[i])%mod;
        }
        else {
            p[i]=(mod+p[i])%mod;
        }
    }
    dp[0]=1;
    for(int i=1;i<(1<<n);i++) {
        int msk=i;
        for(int j=i;j;j=((j-1)&i)) {
            dp[i]+=dp[j^i]*p[j];
            dp[i]%=mod;
        }
    }
    long long ret=dp[(1<<n)-1];
    ret*=m;
    ret%=mod;
    ret*=(mod+1)/2;
    ret%=mod;
    printf("%lld",ret);
    return 0;
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:48:13: warning: unused variable 'msk' [-Wunused-variable]
   48 |         int msk=i;
      |             ^~~
amusementpark.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
amusementpark.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         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