Submission #63058

#	Time	Username	Problem	Language	Result	Execution time	Memory
63058		Bodo171	Paths (BOI18_paths)	C++14	100 / 100	467 ms	51584 KiB

paths

#include <iostream>
#include <fstream>
using namespace std;
const int nmax=300005;
long long dp[32][nmax];
int c[nmax],a[nmax],b[nmax];
int n,m,k,i,j,x,y;
long long ans;
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>m>>k;
    for(i=1;i<=n;i++)
    {
        cin>>c[i];
        c[i]--;
    }
    for(i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i];
    }
    for(j=1;j<=n;j++)
        dp[(1<<c[j])][j]=1;
    for(i=1;i<(1<<k);i++)
    {
        if((i&(i-1)))
          for(j=1;j<=n;j++)
            ans+=dp[i][j];
        for(j=1;j<=m;j++)
       {
             x=a[j];y=b[j];
            if(((1<<c[x])&i)&&(!((1<<c[y])&i)))
               dp[i+(1<<c[y])][y]+=dp[i][x];
            if((!((1<<c[x])&i))&&((1<<c[y])&i))
               dp[i+(1<<c[x])][x]+=dp[i][y];
       }
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30