Submission #651127

#TimeUsernameProblemLanguageResultExecution timeMemory
651127dooompyPaths (BOI18_paths)C++17
100 / 100
956 ms172436 KiB
#include "bits/stdc++.h" using namespace std; void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { while (l != r) cout << *l << " \n"[++l == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.first >> a.second; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.first << ", " << a.second << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } #ifdef local #define test(args...) abc("[" + string(#args) + "]", args) #else #define test(args...) void(0) #endif using ll = long long; int col[300005]; ll dp[300005][1 << 6]; vector<int> adj[300005]; ll total = 0; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("", "r", stdin); // freopen("", "w", stdout); int n, m, k; cin >> n >> m >> k; for (int i = 1; i <= n; i++) { cin >> col[i]; col[i]--; dp[i][1 << col[i]] = 1; } for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } for (int len = 2; len <= k; len++) { for (int i = 1; i <= n; i++) { int curcol = col[i]; for (auto nxt : adj[i]) { for (int mask = 1; mask < (1 << 6); mask++) { if (mask & (1 << curcol)) continue; if (__builtin_popcount(mask) != (len - 1)) continue; dp[i][mask | (1 << curcol)] += dp[nxt][mask]; total += dp[nxt][mask]; } } } } cout << total; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...