Submission #1202293

#TimeUsernameProblemLanguageResultExecution timeMemory
1202293PlayVoltzPaths (BOI18_paths)C++20
100 / 100
316 ms69620 KiB
#include <cstdio> #include <stdio.h> #include <stdbool.h> #include <iostream> #include <map> #include <vector> #include <climits> #include <stack> #include <string> #include <queue> #include <algorithm> #include <set> #include <unordered_set> #include <unordered_map> #include <cmath> #include <cctype> #include <bitset> #include <iomanip> #include <cstring> #include <numeric> #include <cassert> using namespace std; #define int long long #define pii pair<int, int> #define mp make_pair #define pb push_back #define fi first #define se second int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, k, a, b, ans=0; cin>>n>>m>>k; vector<int> vect(n+1); vector<vector<int> > graph(n+1), dp(n+1, vector<int>((1<<k), 0)); for (int i=1; i<=n; ++i)cin>>vect[i], --vect[i]; while (m--){ cin>>a>>b; graph[a].pb(b); graph[b].pb(a); } for (int i=1; i<=n; ++i)dp[i][1<<vect[i]]=1; for (int mask=0; mask<(1<<k); ++mask)for (int i=1; i<=n; ++i)for (auto num:graph[i])if (mask&(1<<vect[num]))dp[i][mask]+=dp[num][mask^(1<<vect[i])]; for (int mask=0; mask<(1<<k); ++mask)for (int i=1; i<=n; ++i)if (__builtin_popcount(mask)>1)ans+=dp[i][mask]; cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...