Submission #1009405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009405		alexdd	Paths (BOI18_paths)	C++17	100 / 100	259 ms	73192 KiB

paths

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int color[300005];
long long dp[5][32][300005];
vector<int> con[300005];
signed main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>color[i];
        color[i]--;
        dp[0][(1<<color[i])][i]=1;
    }
    int u,v;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        con[u].push_back(v);
        con[v].push_back(u);
    }
    for(int pas=1;pas<k;pas++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int mask=(1<<color[i]);mask<(1<<k);mask++)
            {
                if(!dp[pas-1][mask][i])
                    continue;
                for(auto x:con[i])
                {
                    if(!((1<<color[x])&mask))
                        dp[pas][mask+(1<<color[x])][x] += dp[pas-1][mask][i];
                }
            }
        }
    }
    long long rez=0;
    for(int pas=1;pas<k;pas++)
        for(int i=1;i<=n;i++)
            for(int mask=0;mask<(1<<k);mask++)
                rez += dp[pas][mask][i];
    cout<<rez;
    return 0;
}

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