Submission #189111

#	Time	Username	Problem	Language	Result	Execution time	Memory
189111		nicolaalexandra	Paths (BOI18_paths)	C++14	100 / 100	1053 ms	139540 KiB

paths

#include <bits/stdc++.h>
#define DIM 300010
using namespace std;
vector <int> L[DIM];
long long dp[DIM][50];
int n,m,k,i,j,x,y,nr;
int v[DIM];
int main (){

    cin>>n>>m>>k;
    for (i=1;i<=n;i++){
        cin>>v[i];
        dp[i][(1<<(v[i]-1))] = 1;
    }
    for (i=1;i<=m;i++){
        cin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    for (nr=2;nr<=k;nr++){
        /// mai adaug o culoare la masca
        for (i=1;i<=n;i++){
            for (auto vecin:L[i]){
                for (int mask=0;mask<(1<<k);mask++){
                    if (!(mask&(1<<(v[i]-1))) && __builtin_popcount(mask) == nr-1)
                        dp[i][mask|(1<<(v[i]-1))] += dp[vecin][mask];

                }}}}

    long long sol = 0;
    for (i=1;i<=n;i++)
        for (int mask=0;mask<(1<<k);mask++)
            sol += dp[i][mask];

    cout<<sol-n;

    return 0;
}

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