Submission #887676

#TimeUsernameProblemLanguageResultExecution timeMemory
887676votranngocvyPaths (BOI18_paths)C++14
100 / 100
257 ms103096 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 3e5 + 5; int n,m,k,a[N]; vector<int>g[N]; namespace sub1 { int ans = 0; bool vis[10]; void dfs(int u) { vis[a[u]] = true; for (auto v: g[u]) { if (vis[a[v]]) continue; ans++; dfs(v); } vis[a[u]] = false; } void solve() { for (int i = 1; i <= n; i++) dfs(i); cout << ans << "\n"; } } namespace sol { int dp[N][35]; void solve() { for (int i = 1; i <= n; i++) dp[i][(1 << a[i])] = 1; for (int mask = 0; mask < (1 << k); mask++) { for (int u = 1; u <= n; u++) { if (dp[u][mask] == 0) continue; for (auto v: g[u]) { if (mask & (1 << a[v])) continue; dp[v][mask | (1 << a[v])] += dp[u][mask]; } } } int ans = 0; for (int i = 1; i <= n; i++) for (int mask = 0; mask < (1 << k); mask++) if (__builtin_popcount(mask) >= 2) ans += dp[i][mask]; cout << ans << "\n"; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; a[i]--; } for (int i = 1; i <= m; i++) { int u,v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } sol::solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...