Submission #543684

#	Time	Username	Problem	Language	Result	Execution time	Memory
543684		tudor	Paths (BOI18_paths)	C++17	100 / 100	820 ms	97148 KiB

paths

#include <iostream>
#include <vector>

using namespace std;
const int nmax = 3e5;
const int kmax = 5;

long long dp[nmax][1 << kmax];
/// numarul de lanturi care se termina in i si am trecut prin bitii mask
int c[nmax];
vector < int > g[nmax + 1];

int main() {
    int n, m, k, a, b;

    cin >> n >> m >> k;

    for ( int i = 0; i < n; i++ ) {
        cin >> c[i];
        c[i]--;
        dp[i][1 << c[i]] = 1;
    }

    for ( int i = 0; i < m; i++ ) {
        cin >> a >> b;
        a--; b--;
        g[a].push_back ( b );
        g[b].push_back ( a );
    }

    for ( int mask = 1; mask < ( 1 << k ); mask++ )
        for ( int i = 0; i < n; i++ )
            for ( int node: g[i] )
                if ( ! ( mask & ( 1 << c[node] ) ) )
                    dp[node][mask | ( 1 << c[node] )] += dp[i][mask];

    long long s = 0;
    for ( int mask = 1; mask < ( 1 << k ); mask++ )
        if ( mask & ( mask - 1 ) )
            for ( int i = 0; i < n; i++ )
                s = s + dp[i][mask];

    cout << s;

    return 0;
}

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