oj.uz

Submission #1095807

# Submission time Handle Problem Language Result Execution time Memory
1095807 2024-10-03T08:21:31 Z alexander707070 Amusement Park (CEOI19_amusementpark) C++14
0 / 100
 21 ms 42772 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42588 KB Output is correct
2 Correct 21 ms 42728 KB Output is correct
3 Correct 17 ms 42588 KB Output is correct
4 Correct 17 ms 42712 KB Output is correct
5 Incorrect 18 ms 42772 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42588 KB Output is correct
2 Correct 21 ms 42728 KB Output is correct
3 Correct 17 ms 42588 KB Output is correct
4 Correct 17 ms 42712 KB Output is correct
5 Incorrect 18 ms 42772 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42588 KB Output is correct
2 Correct 21 ms 42728 KB Output is correct
3 Correct 17 ms 42588 KB Output is correct
4 Correct 17 ms 42712 KB Output is correct
5 Incorrect 18 ms 42772 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42588 KB Output is correct
2 Correct 21 ms 42728 KB Output is correct
3 Correct 17 ms 42588 KB Output is correct
4 Correct 17 ms 42712 KB Output is correct
5 Incorrect 18 ms 42772 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42588 KB Output is correct
2 Correct 21 ms 42728 KB Output is correct
3 Correct 17 ms 42588 KB Output is correct
4 Correct 17 ms 42712 KB Output is correct
5 Incorrect 18 ms 42772 KB Output isn't correct
6 Halted 0 ms 0 KB -