oj.uz

Submission #1095748

# Submission time Handle Problem Language Result Execution time Memory
1095748 2024-10-03T06:26:51 Z alexander707070 Amusement Park (CEOI19_amusementpark) C++14
0 / 100
 21 ms 42744 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 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.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42588 KB Output is correct
2 Correct 18 ms 42584 KB Output is correct
3 Correct 21 ms 42672 KB Output is correct
4 Incorrect 19 ms 42744 KB Output isn't correct
5 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 18 ms 42584 KB Output is correct
3 Correct 21 ms 42672 KB Output is correct
4 Incorrect 19 ms 42744 KB Output isn't correct
5 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 18 ms 42584 KB Output is correct
3 Correct 21 ms 42672 KB Output is correct
4 Incorrect 19 ms 42744 KB Output isn't correct
5 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 18 ms 42584 KB Output is correct
3 Correct 21 ms 42672 KB Output is correct
4 Incorrect 19 ms 42744 KB Output isn't correct
5 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 18 ms 42584 KB Output is correct
3 Correct 21 ms 42672 KB Output is correct
4 Incorrect 19 ms 42744 KB Output isn't correct
5 Halted 0 ms 0 KB -