Submission #1052453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052453		handlename	Amusement Park (CEOI19_amusementpark)	C++17	42 / 100	309 ms	3408 KiB

amusementpark

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define float long double
// const int MOD=1e9+7;
const int MOD=998244353;
const int sqn=450;
const long double eps=1e-6;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
long long power(long long a,long long b,long long p=MOD){
    long long res=1;
    while (b>0){
        if (b%2==1) res=(res*a)%p;
        b/=2;
        a=(a*a)%p;
    }
    return res;
}
int n,m;
bool adj[20][20],indep[1000001];
// for each legal proposal, reversing the edges creates another
// costs for this pair is m
// sum of costs is m * DAGCount/2
// where DAGCount = number of DAGs on original graph
long long dp[1000001];
// dp[mask] = number of DAGs on graph with mask vertices
// for any DAG, at least 1 vertex has out degree 0
// we loop through all possible subsets of vertices with out degree 0
// this subset must be an independent set
// however, we cannot just add them all up
// as subsets of independent sets are also independent
// to fix double counting, use PIE
void runtc(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        u--;
        v--;
        adj[u][v]=adj[v][u]=true;
    }
    memset(indep,true,sizeof(indep));
    for (int i=0;i<(1<<n);i++){
        for (int j=0;j<n;j++){
            for (int k=j+1;k<n;k++){
                if (!(i&(1<<j))) continue;
                if (!(i&(1<<k))) continue;
                if (adj[j][k]) indep[i]=false;
            }
        }
    }
    dp[0]=1;
    for (int i=1;i<(1<<n);i++){
        vector<int> arr;
        for (int j=0;j<n;j++){
            if (!(i&(1<<j))) continue;
            arr.pb(j);
        }
        // we loop through all independent subsets
        int sz=arr.size();
        for (int j=0;j<(1<<sz);j++){
            int curmask=0,num=0;
            for (int k=0;k<sz;k++){
                if (!(j&(1<<k))) continue;
                curmask^=(1<<arr[k]);
                num++;
            }
            if (!indep[curmask]) continue;
            if (num%2==1){
                dp[i]+=dp[i^curmask];
            }
            else {
                dp[i]-=dp[i^curmask];
            }
            dp[i]%=MOD;
        }
    }
    long long ans=dp[(1<<n)-1];
    ans*=m;
    ans%=MOD;
    ans*=power(2,MOD-2,MOD);
    ans%=MOD;
    cout<<ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("movie.in","r",stdin);
    // freopen("movie.out","w",stdout);
    //freopen("input1.in","r",stdin);
    // freopen("output1.out","w",stdout);
    //freopen("tower_rush_input.txt","r",stdin);
    //freopen("hackercup_output.txt","w",stdout);
    int tcs;
    // cin>>tcs;
    tcs=1;
    for (int i=1;i<=tcs;i++){
        // cout<<"Case #"<<i<<": ";
        runtc();
    }
}

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