This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #pragma GCC optimize("Ofast,unroll-loops")
// el psy congroo
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 3e5+23, inf = INT_MAX, LG = 19;
vector<int> graph[sze];
map<vector<int>,int> var;
vector<int> ord;
int col[sze];
int dp[sze];
int nxt[sze];
void dfs(int node,int idx){
if(idx== (ord.size()-1 ) ){
dp[node]=1;
return;
}
for(auto v:graph[node]){
if(col[v]==ord[idx+1]){
dp[v]=0;
dfs(v,idx+1);
dp[node]+=dp[v];
}
}
}
vector<int> cc[10];
void fast(){
int n,m,k;
cin>>n>>m>>k;
for(int i =1;i<=n;i++){
cin>>col[i];
cc[col[i]].pb(i);
}
int u,v;
for(int i =0;i<m;i++){
cin>>u>>v;
graph[u].pb(v);
graph[v].pb(u);
}
int ans=0;
vector<int> ad;
for(int i =0;i<k;i++){
ad.pb(i+1);
}
// for(auto v:ad) cout<<v<<" ";cout<<endl;
do{
ord.clear();
ord.pb(ad[0]);
for(int i =1;i<k;i++){
ord.pb(ad[i]);
if(!var[ord]){
// for(auto v:ord) cout<<v<<" ,";cout<<endl;
for(int j=1;j<=n;j++){
dp[j]=0;
}
for(auto v:cc[ord[0]]){
dfs(v,0);
if(dp[v]){
// cout<<v<<" == "<<dp[v]<<endl;
ans=(ans+dp[v])%mod;
}
}
var[ord]=1;
}
}
}while(next_permutation(all(ad)));
putr(ans);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt = 1;
// cin>>tt;
while(tt--){
fast();
}
return 0;
}
Compilation message (stderr)
paths.cpp: In function 'void dfs(long long int, long long int)':
paths.cpp:22:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | if(idx== (ord.size()-1 ) ){
| ~~~^~~~~~~~~~~~~~~~~~
# | 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... |