Submission #349000

#	Time	Username	Problem	Language	Result	Execution time	Memory
349000		blue	Paths (BOI18_paths)	C++17	100 / 100	722 ms	52076 KiB

paths

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int N, M, K;
    cin >> N >> M >> K;

    vector<int> col(N+1);
    for(int i = 1; i <= N; i++)
    {
        cin >> col[i];
        col[i] = (1 << (col[i] - 1));
    }

    vector<int> edge[N+1];
    int a, b;
    for(int i = 1; i <= M; i++)
    {
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }



    vector<int> count1(33);
    count1[0] = 0;
    for(int i = 1; i <= 32; i++) count1[i] = count1[i/2] + (i % 2);


    vector< vector<int> > dp = vector< vector<int> >(N+1, vector<int>((1 << K), 0));


    for(int mask = 1; mask < (1 << K); mask++)
    {
        for(int u = 1; u <= N; u++)
        {
            if(mask & col[u])
            {
                if(count1[mask] == 1) dp[u][mask] = 1;
                else for(int v: edge[u]) dp[u][mask] += dp[v][mask - col[u]];
            }

            // cout << u << ' ' << col[u] << ' ' << bool(mask&1) << bool(mask&2) << bool(mask&4) << ' ' << dp[u][mask] << '\n';
        }
    }


    long long res = 0;

    for(int i = 1; i <= N; i++)
    {
        for(int mask = 0; mask < (1 << K); mask++)
        {
            if(count1[mask] > 1)
                res += dp[i][mask];
        }
    }

    cout << res << '\n';
}

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