# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1265961 | warrenn | Paths (BOI18_paths) | C11 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k;
int dp[300002][32];
int col[300002];
vector<int>adj[300002];
signed main(){
cin>>n>>m>>k;
for(int q=1;q<=n;q++){
cin>>col[q];
col[q]--;
dp[q][(1<<col[q])]=1;
}
for(int q=1;q<=m;q++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int ans=0;
for(int mask=0;mask<(1<<k);mask++){
for(int idx=1;idx<=n;idx++){
for(auto nxt : adj[idx]){
if((mask>>col[nxt])&1){
}
else{
dp[nxt][mask+(1<<col[nxt])]+=dp[idx][mask];
}
}
ans+=dp[idx][mask];
}
}
cout<<ans-n<<endl;
}