fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
  5. #define bit(mask, i) ((mask >> i) & 1)
  6.  
  7.  
  8. const int maxn = 1e5 + 5;
  9.  
  10.  
  11.  
  12. int n, m, k;
  13. int c[maxn];
  14. long long dp[maxn][1 << 6];
  15. vector<int> a[maxn];
  16.  
  17.  
  18. signed main() {
  19.     ios::sync_with_stdio(0);
  20.     cin.tie(0); cout.tie(0);
  21.  
  22.  
  23.  
  24.     cin >> n >> m >> k;
  25.  
  26.     FOR(i, 1, n) cin >> c[i], --c[i];
  27.  
  28.  
  29.     FOR(i, 1, m) {
  30.         int u, v; cin >> u >> v;
  31.         a[u].push_back(v);
  32.         a[v].push_back(u);
  33.     }
  34.  
  35.  
  36.  
  37.  
  38.  
  39.     FOR(i, 1, n) dp[i][1 << c[i]] = 1;
  40.  
  41.  
  42.  
  43.  
  44.     long long ans = 0;
  45.     FOR(mask, 0, (1 << k) - 1) {
  46.         FOR(i, 1, n) {
  47.             if (!bit(mask, c[i])) continue;
  48.  
  49.             int cur_mask = mask ^ (1 << c[i]);
  50.             for (int j : a[i]) {
  51.                 if (i == j) continue;
  52.                 if (!bit(cur_mask, c[j])) continue;
  53.  
  54.  
  55.                 dp[i][mask] += dp[j][cur_mask];
  56.             }
  57.             ans += dp[i][mask];
  58.         }
  59.     }
  60.  
  61.  
  62.  
  63.     ans -= n;
  64.     cout << ans;
  65.  
  66.  
  67.  
  68.     return 0;
  69. }
Success #stdin #stdout 0.01s 7900KB
comments (?)
stdin
copy 
4 3 3
1 2 1 3
1 2
2 3
4 2
stdout
copy 
10
https://ideone.com/U5BU8U
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!