Submission #696780

#TimeUsernameProblemLanguageResultExecution timeMemory
696780vjudge1Amusement Park (CEOI19_amusementpark)C++17
100 / 100
2377 ms3720 KiB
#include<bits/stdc++.h> using namespace std; const int N=18,mod=998244353,inv2=499122177; int n,m,a[500],b[500],coef[1<<N],dp[1<<N],d[1<<N]; int main(){ scanf("%d%d",&n,&m); dp[0]=1; coef[0]=mod-1; for(int i=1;i<1<<n;i++)coef[i]=mod-coef[i&(i-1)]; for(int i=1;i<=m;i++)scanf("%d%d",&a[i],&b[i]),a[i]--,b[i]--; for(int i=1;i<1<<n;i++){ for(int o=1;o<=m;o++){ if((i>>a[o]&1)&&(i>>b[o]&1))d[i]=1; } } for(int i=1;i<1<<n;i++){ for(int o=i;o;o=((o-1)&i)){ if(!d[o])dp[i]=(dp[i]+1ll*dp[i^o]*coef[o])%mod; } } printf("%lld\n",1ll*dp[(1<<n)-1]*m%mod*inv2%mod); return 0; }

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:6:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
amusementpark.cpp:10:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  for(int i=1;i<=m;i++)scanf("%d%d",&a[i],&b[i]),a[i]--,b[i]--;
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...