#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 3e5 + 10;
int color[MAXN];
vector<int> adj[MAXN];
ll dp[5][MAXN];
int n, m;
ll solve(vector<int> c){
ll r = 0;
int K = (int) c.size();
do{
for(int k=0; k<K; k++){
for(int i=1; i<=n; i++){
dp[k][i] = 0;
if(k == K - 1 && color[i] == c[k]) dp[k][i] = 1;
}
}
for(int k=K-2; k>=0; k--){
for(int i=1; i<=n; i++){
if(color[i] == c[k]){
for(auto j : adj[i]){
if(color[j] == c[k + 1]){
dp[k][i] += dp[k + 1][j];
}
}
}
if(k == 0) r += dp[k][i];
}
}
} while(next_permutation(c.begin(), c.end()));
return r;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int k; cin >> n >> m >> k;
for(int i=1; i<=n; i++) cin >> color[i];
for(int i=1; i<=m; i++){
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
ll ans = 0;
for(int a=1; a<=k; a++){
for(int b=a+1; b<=k; b++){
ans += solve({a, b});
for(int c=b+1; c<=k; c++){
ans += solve({a, b, c});
for(int d=c+1; d<=k; d++){
ans += solve({a, b, c, d});
for(int e=d+1; e<=k; e++){
ans += solve({a, b, c, d, e});
}
}
}
}
}
cout << ans << "\n";
return 0;
}
# | 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... |