Submission #1066708

#TimeUsernameProblemLanguageResultExecution timeMemory
1066708vjudge1Amusement Park (CEOI19_amusementpark)C++17
100 / 100
797 ms3668 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; bitset<1<<18>indep; ll dp[1<<18]; const ll mod=998244353; int EDG[19][19],PC[1<<18]; int main(){ int n,m; cin>>n>>m; for(int i=0;i<m;i++){ int a,b; cin>>a>>b; EDG[a][b]=1; EDG[b][a]=1; } for(int i=1;i<1<<n;i++){ vector<int>v; for(int j=0;j<n;j++) if(i&1<<j) v.push_back(j+1); int bad=0; for(auto k:v) for(auto j:v) bad|=EDG[k][j]; indep[i]=!bad; PC[i]=__builtin_popcount(i)&1?1:-1; } dp[0]=1; for(int i=1;i<1<<n;i++) for(int j=i;j;j=j-1&i) dp[i]+=dp[i^j]*PC[j]*indep[j]; cout<<dp[(1<<n)-1]%mod*((mod+1)/2)%mod*m%mod; }

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:31:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   31 |         for(int j=i;j;j=j-1&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...