# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
173519 | rzbt | Paths (BOI18_paths) | C++14 | 549 ms | 107512 KiB |
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 mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 300005
typedef long long ll;
using namespace std;
vector<ll> niz[MAXN];
ll dp[MAXN][35];
ll koji[MAXN];
ll n,m,k;
ll res=0;
int main()
{
scanf("%lld %lld %lld", &n, &m, &k);
for(ll i=1;i<=n;i++){
ll t;
scanf("%lld", &t);
t--;
dp[i][1<<t]=1;
koji[i]=1<<t;
}
for(ll i=1;i<=m;i++){
ll t1,t2;
scanf("%lld %lld", &t1, &t2);
niz[t1].pb(t2);
niz[t2].pb(t1);
}
for(ll j=1;j<(1<<k);j++){
for(ll i=1;i<=n;i++){
if(!(koji[i]&j))continue;
for(auto x:niz[i]){
dp[i][j]+=dp[x][j-koji[i]];
}
res+=dp[i][j];
//printf(" %lld %lld %lld\n",i,j,dp[i][j]);
}
}
printf("%lld",res-n);
return 0;
}
Compilation message (stderr)
# | 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... |