Submission #791544

#	Time	Username	Problem	Language	Result	Execution time	Memory
791544		vgoofficial	Amusement Park (CEOI19_amusementpark)	C++14	100 / 100	1681 ms	4700 KiB

amusementpark

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 998244353;
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    vector<int> connections(n);
    for(int i = 0; i < m; i++) {
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        connections[a]|=1<<b;
        connections[b]|=1<<a;
    }
    bool indep[1<<n];
    int bitCount[1<<n];
    int pm1[1<<n];
    for(int i = 0; i < 1<<n; i++) {
        indep[i]=true;
        bitCount[i]=__builtin_popcount(i);
        for(int j = 0; j < n; j++) {
            if((i&(1<<j))!=0) {
                if((connections[j]&(i^(1<<j)))!=0) {
                    indep[i]=false;
                    break;
                }
            }
        }
        pm1[i]=(bitCount[i]%2==0? -1:1);
    }
    vector<ll> numAcyclicGraphs(1<<n);
    numAcyclicGraphs[0]=1;
    for(int i = 0; i < 1<<n; i++) {
        for(int j = i; j!=0; j=((j-1)&i))  {
            int without = i^j;
            if(!indep[j]) continue;
            //cout << i << " " << j << endl;
            numAcyclicGraphs[i]=(numAcyclicGraphs[i]+pm1[j]*numAcyclicGraphs[without])%mod;
        }
        while(numAcyclicGraphs[i]<0) numAcyclicGraphs[i]+=mod;
    }
    cout << numAcyclicGraphs[(1<<n)-1] * m % mod * (mod+1)/2 % mod << endl;
}

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