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<iostream>
#include<vector>
using namespace std;
long long Dp[35][300005];
int Col[300005];
vector<int> A[300005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,k;
cin>>n>>m>>k;
for(int i=1; i<=n; i++)
{
cin>>Col[i];
Col[i]--;
Dp[1<<Col[i]][i]=1;
}
for(int i=1; i<=m; i++)
{
int x,y;
cin>>x>>y;
A[x].push_back(y);
A[y].push_back(x);
}
long long rez=0;
for(int conf=1; conf<(1<<k); conf++) //tot timpul o sa parcurg config din care se poate obtine conf inainte de conf
{
for(int i=1; i<=n; i++)
{
if(Dp[conf][i]==0)
continue;
rez+=Dp[conf][i];
for(auto other:A[i])
{
if(conf&(1<<Col[other]))
continue;
Dp[conf^(1<<Col[other])][other]+=Dp[conf][i];
}
}
}
cout<<rez-n<<"\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... |