Submission #1108300

#TimeUsernameProblemLanguageResultExecution timeMemory
1108300overwatch9Paths (BOI18_paths)C++17
23 / 100
3067 ms15188 KiB
#include <bits/stdc++.h> using namespace std; int n, m, k; const int maxn = 3e5+1; vector <int> adj[maxn]; int col[maxn]; int cnt; bool vis[maxn]; void solve(int s, int p, int x, int len, int has) { if (vis[s] || len > k) return; vis[s] = true; if (len > 1) cnt++; for (auto i : adj[s]) { if (i == p) continue; if (has & (1 << col[i])) continue; solve(i, s, x + (1 << len) * col[i], len + 1, has + (1 << col[i])); } vis[s] = false; } int main() { cin >> n >> m >> k; for (int i = 1; i <= n; i++) cin >> col[i]; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } for (int i = 1; i <= n; i++) solve(i, i, col[i], 1, (1 << col[i])); cout << cnt << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...