Submission #485554

#	Time	Username	Problem	Language	Result	Execution time	Memory
485554		chungdinh	Paths (BOI18_paths)	C++17	100 / 100	430 ms	61344 KiB

paths

#include <iostream>
#include <vector>

#define ll long long

const int N = 5e5 + 5;
const ll MOD = 1e9 + 7;

#define cntbit(x) __builtin_popcount(x)
#define on(b, x) (b & (1 << x))

using namespace std;

int n, m, k;
int c[N];
vector<int> g[N];

ll dp[1 << 5][N];

vector<int> z[100];

int main() {
    #ifdef CHUNGDINH
    freopen("main.inp", "r", stdin);
    #endif // CHUNGDINH

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> c[i]; c[i]--;
        dp[1 << c[i]][i] = 1;
    }
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int b = 1; b < (1 << k); b++) z[cntbit(b)].push_back(b);

    ll res = 0;

    for (int i = 2; i <= k; i++) {
        for (int b : z[i]) {
            for (int u = 1; u <= n; u++) {
                dp[b][u] = 0;
                if (!on(b, c[u])) continue;

                for (int v : g[u]) {
                    if (!on(b, c[v])) continue;
                    dp[b][u] += dp[b ^ (1 << c[u])][v];
                }

                res += dp[b][u];
            }
        }
    }

    cout << res;
}

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