Submission #676898

#	Time	Username	Problem	Language	Result	Execution time	Memory
676898		Cyanmond	Paths (BOI18_paths)	C++17	100 / 100	423 ms	57664 KiB

paths

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    int N, M, K;
    std::cin >> N >> M >> K;
    std::vector<int> C(N);
    for (auto &e : C) {
        std::cin >> e;
        --e;
    }
    std::vector<int> U(M), V(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> U[i] >> V[i];
        --U[i], --V[i];
    }

    std::vector dp(N, std::vector(1 << K, 0ll));
    for (int i = 0; i < N; ++i) {
        dp[i][1 << C[i]] = 1;
    }

    for (int bit = 0; bit < (1 << K); ++bit) {
        for (int i = 0; i < M; ++i) {
            const int a = U[i], b = V[i];
            const int ca = C[a], cb = C[b];
            const bool x = bit & (1 << ca), y = bit & (1 << cb);
            if (x and not y) {
                dp[b][bit | (1 << cb)] += dp[a][bit];
            }
            if (not x and y) {
                dp[a][bit | (1 << ca)] += dp[b][bit];
            }
        }
    }

    i64 answer = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < (1 << K); ++j) {
            if (__builtin_popcount(j) > 1) {
                answer += dp[i][j];
            }
        }
    }

    std::cout << answer << std::endl;
}

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