Submission #823109

#TimeUsernameProblemLanguageResultExecution timeMemory
823109Desh03Paths (BOI18_paths)C++17
23 / 100
3040 ms3084 KiB
#include <bits/stdc++.h> using namespace std; vector<vector<int>> g, cnt; vector<int> c; vector<bool> vis; void dfs(int u, int mask, const bool &z) { vis[u] = 1; ++cnt[z][mask]; for (int v : g[u]) { if (!vis[v] && !(mask >> c[v] & 1)) { dfs(v, mask | (1 << c[v]), z); } } vis[u] = 0; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m, k; cin >> n >> m >> k; g.resize(n), cnt.resize(2, vector<int> (1 << k)), c.resize(n), vis.resize(n); for (int i = 0; i < n; i++) { cin >> c[i]; --c[i]; } long long ans = 0; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; --u, --v; vis[v] = 1; dfs(u, 1 << c[u], 0); vis[u] = 1; dfs(v, 1 << c[v], 1); vis[u] = 0; for (int mask = 0; mask < (1 << k); mask++) { for (int mask2 = 0; mask2 < (1 << k); mask2++) { if ((mask & mask2) == 0) { ans += cnt[0][mask] * cnt[1][mask2] << 1; } } } for (int j : {0, 1}) for (int &x : cnt[j]) x = 0; g[u].push_back(v); g[v].push_back(u); } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...