Submission #566227

#TimeUsernameProblemLanguageResultExecution timeMemory
566227hollwo_pelwPaths (BOI18_paths)C++17
100 / 100
325 ms52504 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/trie_policy.hpp> // #include <ext/rope> using namespace std; // using namespace __gnu_cxx; // using namespace __gnu_pbds; void Hollwo_Pelw(); signed main(){ #ifndef hollwo_pelw_local if (fopen(".inp", "r")) assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout)); #else using namespace chrono; auto start = steady_clock::now(); #endif cin.tie(0), cout.tie(0) -> sync_with_stdio(0); int testcases = 1; // cin >> testcases; for (int test = 1; test <= testcases; test++){ // cout << "Case #" << test << ": "; Hollwo_Pelw(); } #ifdef hollwo_pelw_local auto end = steady_clock::now(); cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl; #endif } const int N = 3e5 + 5; long long dp[1 << 5][N], res; int n, m, k, c[N]; vector<int> adj[N]; void Hollwo_Pelw(){ cin >> n >> m >> k; for (int i = 1; i <= n; i++) cin >> c[i], c[i] --; for (int u, v; m --; ) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } for (int i = 1; i <= n; i++) dp[1 << c[i]][i] = 1; for (int mask = 1; mask < 1 << k; mask++) { for (int u = 1; u <= n; u++) if (dp[mask][u]) { res += dp[mask][u]; for (int v : adj[u]) if ((mask >> c[v] & 1) == 0) dp[mask ^ 1 << c[v]][v] += dp[mask][u]; } } cout << res - n << '\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...