This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 3e5+10;
int a[N], color[N], n, m, k;
vector<int> edges[N];
long long dp[32][N];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> k;
for(int i = 0; i < n; ++i) {
cin >> color[i];
--color[i];
}
for(int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
edges[u].push_back(v);
edges[v].push_back(u);
}
for(int i = 0; i < n; ++i) {
dp[1 << color[i]][i] = 1;
}
for(int mask = 1; mask < (1 << k); ++mask) {
for(int x = 0; x < n; ++x) {
int bit = color[x];
if(mask >> bit & 1) {
int submask = mask ^ (1 << bit);
for(int i : edges[x]) {
dp[mask][x] += dp[submask][i];
}
}
}
}
long long ans = -n;
for(int mask = 0; mask < (1 << k); ++mask) {
for(int x = 0; x < n; ++x) {
ans += dp[mask][x];
}
}
cout << ans << endl;
}
# | 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... |