Submission #1066674

#TimeUsernameProblemLanguageResultExecution timeMemory
1066674vjudge1Amusement Park (CEOI19_amusementpark)C++17
42 / 100
11 ms604 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; bitset<1<<18>indep; ll dp[1<<18]; const int mod=1e9+7; int EDG[20][20]; 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; } 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 i:v) for(auto j:v) if(EDG[i][j]) bad=1; indep[i]=!bad; } dp[0]=1; for(int i=1;i<1<<n;i++) for(int j=i;j;j=j-1&i){ if(!indep[j])continue; int cnt=__builtin_popcount(j); dp[i]=(dp[i]+dp[i^j]*(cnt&1?1:-1))%mod; } cout<<dp[(1<<n)-1]*m%mod*(ll)(5e8+4)%mod<<'\n'; }

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:30:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   30 |         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...