Submission #1136616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136616		TrinhKhanhDung	Paths (BOI18_paths)	C++20	100 / 100	304 ms	66348 KiB

paths

#include <bits/stdc++.h>

using namespace std;

void solve(){
    int N, M, K; cin >> N >> M >> K;
    vector<int> color(N);
    for(int i = 0; i < N; i++){
        cin >> color[i];
        color[i]--;
    }
    vector<vector<int>> adj(N);
    for(int i = 0; i < M; i++){
        int u, v; cin >> u >> v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<vector<long long>> dp(N, vector<long long>(1 << K));
    for(int i = 0; i < N; i++){
        dp[i][1 << color[i]] = 1;
    }
    for(int i = 1; i < K; i++){
        for(int u = 0; u < N; u++){
            for(int mask = 0; mask < (1 << K); mask++){
                if(__builtin_popcount(mask) != i) continue;
                for(int v: adj[u]){
                    if(((mask >> color[v]) & 1) == 0){
                        dp[v][mask | (1 << color[v])] += dp[u][mask];
                    }
                }
            }
        }
    }

    long long ans = 0;
    for(int u = 0; u < N; u++){
        for(int mask = 0; mask < (1 << K); mask++){
            if(__builtin_popcount(mask) < 2) continue;
            ans += dp[u][mask];
        }
    }
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("SHIP.inp", "r", stdin);
//    freopen("SHIP.out", "w", stdout);

    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

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