Submission #1095807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095807		alexander707070	Amusement Park (CEOI19_amusementpark)	C++14	0 / 100	21 ms	42772 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 li2[20][2000000];
pair<int,int> dp2[20][2000000];

int power[20];

int bit(int x,int j){
    return (x/power[j])%3;
}

int cost(int x,int mask){
    int res=0;

    for(int i:r[x]){
        if(bit(mask,i)==1)res++;
    }

    return res;
}

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);
pair<int,int> ff2(int x,int 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);

        r[b].push_back(a);
    }

    power[0]=1;
    for(int i=1;i<20;i++){
        power[i]=power[i-1]*3;
    }

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

    return 0;
}

pair<int,int> ff(int mask){
    if(mask==(1<<n)-1)return {0,1};

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

    int mask2=0;

    for(int i=0;i<n;i++){
        if(((1<<i)&mask)>0)continue;
        mask2+=power[i];
    }

    dp[mask]=ff2(0,mask2);

    return dp[mask];
}

pair<int,int> ff2(int x,int mask){
    if(x==n){
        int res=0,br=0;

        for(int i=0;i<n;i++){
            if(bit(mask,i)==2)br++;
            if(bit(mask,i)!=1)res|=(1<<i);
        }

        if(br>0)return ff(res);
        else return {0,0};
    }

    if(li2[x][mask])return dp2[x][mask];
    li2[x][mask]=true;

    dp2[x][mask]=ff2(x+1,mask);

    if(bit(mask,x)==0)return dp2[x][mask];

    bool ok=true,ok2=false;
    for(int i:v[x]){
        if(bit(mask,i)==2)ok=false;
        if(bit(mask,i)==0)ok2=true;
    }

    for(int i=0;i<n;i++){
        if(bit(mask,i)==0)break;
        else if(i==n-1)ok2=true;
    }

    if(!ok or !ok2)return dp2[x][mask];

    dp2[x][mask]=combine(dp2[x][mask],ff2(x+1,mask+power[x]),cost(x,mask));

    return dp2[x][mask];
}

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