Submission #1107590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107590		jadai007	Paths (BOI18_paths)	C++17	100 / 100	259 ms	100424 KiB

paths

#include<bits/stdc++.h>
#define int long long

using namespace std;

int n, m, k, color[300300], ans, dp[300300][32];
vector<int> vc[300300];

int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; ++i) cin >> color[i], color[i]--;
    for(int i = 0; i < m; ++i){
        int u, v; cin >> u >> v;
        vc[u].push_back(v), vc[v].push_back(u);
    }
    for(int i = 1; i <= n; ++i) dp[i][(1<<color[i])] = 1;
    for(int mask = 0; mask < (1<<k); ++mask){
        for(int i = 1; i <= n; ++i){
            for(auto v:vc[i]){
                if(mask&(1<<color[v])) dp[v][mask] += dp[i][mask^(1<<color[v])];
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i) for(int j = 0; j < (1<<k); ++j) ans += dp[i][j];
    cout << ans - n;
}   

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