Submission #564743

#TimeUsernameProblemLanguageResultExecution timeMemory
564743colossal_pepePaths (BOI18_paths)C++17
100 / 100
659 ms70800 KiB
#include <iostream> #include <vector> using namespace std; using ll = long long; int n, m, k; vector<int> c; vector<vector<int>> g; ll solve() { vector<vector<ll>> dp(n, vector<ll>((1 << k), 0)); for (int u = 0; u < n; u++) { dp[u][(1 << c[u])] = 1; } ll ans = 0; for (int i = 2; i <= k; i++) { for (int u = 0; u < n; u++) { for (int v : g[u]) { if (c[u] == c[v]) continue; for (int mask = 0; mask < (1 << k); mask++) { if (__builtin_popcount(mask) == i and mask&(1 << c[u]) and mask&(1 << c[v])) { ans += dp[v][mask - (1 << c[u])]; dp[u][mask] += dp[v][mask - (1 << c[u])]; } } } } } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> k; c.resize(n), g.resize(n); for (int u = 0; u < n; u++) { cin >> c[u]; c[u]--; } while (m--) { int u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } cout << solve() << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...