Submission #1096565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096565		alexander707070	Amusement Park (CEOI19_amusementpark)	C++14	42 / 100	3041 ms	596 KiB

amusementpark

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

const int mod=998244353;

struct polynom{
    int coef[20]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

    inline friend polynom operator - (polynom fr,polynom sc){
        for(int i=0;i<20;i++)fr.coef[i]-=sc.coef[i];
        return fr;
    }
}chromatic;

struct graph{
    bool e[20][20];  
}g;

int n,m,a[4000],b[4000];
long long ans;

graph combine(graph g,int u,int v){

    for(int i=1;i<=n;i++){
        if(i==v)continue;

        if(g.e[v][i]){
            g.e[v][i]=false;
            g.e[i][v]=false;

            g.e[u][i]=true;
            g.e[i][u]=true;
        }
    }
    g.e[v][v]=false;

    return g;
}

polynom build(graph g){

    for(int i=1;i<=n;i++){
        for(int f=i+1;f<=n;f++){
            if(!g.e[i][f])continue;

            g.e[i][f]=g.e[f][i]=false;
            return build(g) - build(combine(g,i,f));
        }
    }

    int br=0;
    for(int i=1;i<=n;i++){
        if(g.e[i][i])br++;
    }


    polynom curr;
    curr.coef[br]++;
    return curr;
}

int main(){

    cin>>n>>m;
    
    for(int i=1;i<=n;i++)g.e[i][i]=true;

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

        g.e[a[i]][b[i]]=true;
        g.e[b[i]][a[i]]=true;
    }

    chromatic=build(g);

    for(int i=19;i>=0;i--){
        if(i%2==0)ans+=chromatic.coef[i];
        else ans-=chromatic.coef[i];
    }

    ans=abs(ans);
    ans*=m; ans/=2; ans%=mod;

    cout<<ans<<"\n";

    return 0;
}

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