Submission #991818

#	Time	Username	Problem	Language	Result	Execution time	Memory
991818		boyliguanhan	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	1614 ms	3676 KiB

amusementpark

#include<bits/stdc++.h>
using namespace std;
int has[18][18],indep[1<<18];
long long dp[1<<18],mod=998244353;
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        x--,y--;
        has[x][y]=1;
        has[y][x]=1;
    }
    for(int i=0;i<1<<n;i++){
        vector<int>v;
        for(int j=0;j<n;j++)
            if(i&1<<j)
                v.push_back(j);
        for(int j=0;j<v.size();j++)
            for(int k=j+1;k<v.size();k++)
                indep[i]|=has[v[j]][v[k]];
        indep[i]^=1;
    }
    dp[0]=1;
    for(int i=1;i<1<<n;dp[i++]%=mod)
        for(int j=i-1&i;;j=j-1&i){
            int cnt=__builtin_popcount(i^j);
            dp[i]=(dp[i]+mod+indep[i-j]*dp[j]*(cnt%2*2-1));
            if(!j) break;
        }
    cout<<(mod+1)/2*dp[(1<<n)-1]%mod*m%mod;
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for(int j=0;j<v.size();j++)
      |                     ~^~~~~~~~~
amusementpark.cpp:21:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             for(int k=j+1;k<v.size();k++)
      |                           ~^~~~~~~~~
amusementpark.cpp:27:20: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   27 |         for(int j=i-1&i;;j=j-1&i){
      |                   ~^~
amusementpark.cpp:27:29: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   27 |         for(int j=i-1&i;;j=j-1&i){
      |                            ~^~

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