Submission #977061

#	Time	Username	Problem	Language	Result	Execution time	Memory
977061		VMaksimoski008	Paths (BOI18_paths)	C++17	100 / 100	482 ms	98424 KiB

paths

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll dp[300005][1<<5], val[300005];

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

    for(int i=0; i<n; i++) cin >> val[i], val[i]--;

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

    for(int i=0; i<n; i++) dp[i][1<<val[i]] = 1;

    for(int s=0; s<(1<<k); s++) {
        for(int i=0; i<n; i++) {
            if((s & (1 << val[i])) == 0) continue;
            for(int &j : graph[i]) {
                if((s & (1 << val[j])) == 0 || val[j] == val[i]) continue;
                dp[i][s] += dp[j][s^(1<<val[i])];
            }
        }
    }

    ll ans = 0;
    for(int i=0; i<n; i++)
        for(int j=0; j<(1<<k); j++)
            if(__builtin_popcount(j) > 1) ans += dp[i][j];
    cout << ans << '\n';
    return 0;
}

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