Submission #391125

#TimeUsernameProblemLanguageResultExecution timeMemory
391125nikatamlianiPaths (BOI18_paths)C++14
100 / 100
406 ms56772 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const ll N = 3e5+10; int a[N], color[N], n, m, k; vector<int> edges[N]; long long dp[32][N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for(int i = 0; i < n; ++i) { cin >> color[i]; --color[i]; } for(int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; --u, --v; edges[u].push_back(v); edges[v].push_back(u); } for(int i = 0; i < n; ++i) { dp[1 << color[i]][i] = 1; } for(int mask = 1; mask < (1 << k); ++mask) { for(int x = 0; x < n; ++x) { int bit = color[x]; if(mask >> bit & 1) { int submask = mask ^ (1 << bit); for(int i : edges[x]) { dp[mask][x] += dp[submask][i]; } } } } long long ans = -n; for(int mask = 0; mask < (1 << k); ++mask) { for(int x = 0; x < n; ++x) { ans += dp[mask][x]; } } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...