Submission #909099

#	Time	Username	Problem	Language	Result	Execution time	Memory
909099		ibm2006	Amusement Park (CEOI19_amusementpark)	C++17	63 / 100	3090 ms	43572 KiB

amusementpark

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod=998244353;
ll n,i,j,a[1100][1100],k,l,r,x,y,z,w,s,t,m,b[1100000],bc[1100000],dp[1100000],c[1100000],ans;
vector<ll> v[1100000],u;
vector<ll> f(ll x)
{
    vector<ll> v,u;
    ll i,y=x,z=1,j;
    for(i=1;i<=n;i++)
    {
        if(y&1)
        {
            v.push_back(1<<(i-1));
        }
        y>>=1;
    }
    u.push_back(0);
    for(i=0;i<v.size();i++)
    {
        z=u.size();
        for(j=0;j<z;j++)
        {
            u.push_back(u[j]+v[i]);
        }
    }
    return u;
}
int main()
{
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%lld %lld",&x,&y);
        a[x][y]=1;
        a[y][x]=1;
    }
    t=1;
    for(i=1;i<=n;i++)
    {
        t*=2;
    }
    for(i=0;i<t;i++)
    {
        x=i;
        s=0;
        for(j=1;j<=n;j++)
        {
            b[j]=x&1;
            s+=x&1;
            x>>=1;
        }
        bc[i]=s;
        v[s].push_back(i);
        c[i]=1;
        for(j=1;j<=n;j++)
        {
            for(k=j+1;k<=n;k++)
            {
                if(b[j]==1&&b[k]==1&&a[j][k]==1)
                    c[i]=0;
            }
        }
    }
    dp[0]=1;
    for(l=1;l<=n;l++)
    {
        for(j=0;j<v[l].size();j++)
        {
            x=v[l][j];
           // printf("%lld ",x);
            u=f(x);
            for(i=0;i<u.size();i++)
            {
               // printf("[%lld,%lld]",u[i],c[u[i]]*dp[x-u[i]]);
                if(u[i]==0)
                    continue;
                if(bc[u[i]]&1)
                {
                    dp[x]+=c[u[i]]*dp[x-u[i]];
                }
                else
                    dp[x]-=c[u[i]]*dp[x-u[i]];
                    dp[x]=(dp[x]%mod+mod)%mod;
            }
           // printf("(%lld) ",dp[x]);
        }
      //  printf("\n");
    }
    ans=dp[t-1]*(mod+1)/2%mod*m%mod;
    printf("%lld",ans);
}

Compilation message (stderr)

amusementpark.cpp: In function 'std::vector<long long int> f(ll)':
amusementpark.cpp:20:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(i=0;i<v.size();i++)
      |             ~^~~~~~~~~
amusementpark.cpp: In function 'int main()':
amusementpark.cpp:69:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(j=0;j<v[l].size();j++)
      |                 ~^~~~~~~~~~~~
amusementpark.cpp:74:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for(i=0;i<u.size();i++)
      |                     ~^~~~~~~~~
amusementpark.cpp:83:17: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   83 |                 else
      |                 ^~~~
amusementpark.cpp:85:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   85 |                     dp[x]=(dp[x]%mod+mod)%mod;
      |                     ^~
amusementpark.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
amusementpark.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%lld %lld",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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