Submission #1095748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095748		alexander707070	Amusement Park (CEOI19_amusementpark)	C++14	0 / 100	21 ms	42744 KiB

amusementpark

#include<bits/stdc++.h>
#define MAXN 600007
using namespace std;

const int mod=998244353;

int n,m,a,b;
vector<int> v[MAXN],g[MAXN],r[MAXN];

pair<int,int> dp[1<<20];
bool li[1<<20];

bool u[20][1<<20];
int calc[20][1<<20];

int cost(int x,int mask){
    if(u[x][mask])return calc[x][mask];
    u[x][mask]=true;

    for(int i:r[x]){
        if(((1<<i)&mask)==0)calc[x][mask]++;
    }

    return calc[x][mask];
}

pair<int,int> combine(pair<int,int> fr,pair<int,int> sc,int s){
    fr.first+=sc.first+sc.second*s;
    fr.first%=mod;

    fr.second+=sc.second;
    fr.second%=mod;

    return fr;
}

pair<int,int> ff(int mask){

    if(li[mask])return dp[mask];
    li[mask]=true;

    for(int i=0;i<n;i++){
        if(((1<<i)&mask)>0)continue;

        bool ok=false;
        for(int f:v[i]){
            if(((1<<f)&mask)==0){
                ok=true; break;
            }
        }

        if(!ok)continue;

        dp[mask]=combine(dp[mask],ff(mask|(1<<i)),cost(i,mask));
    }

    if(dp[mask].second==0){
        dp[mask]={0,1};
    }

    return dp[mask];
}

int main(){

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        a--; b--;

        v[a].push_back(b);
        v[b].push_back(a);

        g[a].push_back(b);
        r[b].push_back(a);
    }

    cout<<ff(0).first<<"\n";

    return 0;
}

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