#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<int> c (n+1, 0);
for (int i = 1; i <= n; i++) {
cin >> c[i];
c[i]--;
}
vector<vector<int>> g (n+1);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
vector<vector<bool>> odw (n+1, vector<bool>(1<<k, 0));
vector<vector<ll>> l (n+1, vector<ll>(1<<k, 0));
queue<pair<int, int>> q;
for (int i = 1; i <= n; i++) {
q.push({i, 1<<c[i]});
l[i][1<<c[i]]++;
}
ll w = 0;
while (!q.empty()) {
auto x = q.front();
q.pop();
if (odw[x.first][x.second]) {
continue;
}
odw[x.first][x.second] = 1;
//cout << x.first << ' ' << x.second << ' ' << l[x.first][x.second] << '\n';
w += l[x.first][x.second];
for (int i : g[x.first]) {
if (!((1<<c[i])&x.second)) {
l[i][(1<<c[i])|x.second] += l[x.first][x.second];
q.push({i, (1<<c[i])|x.second});
}
}
}
cout << w-n << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |