Submission #227631

#TimeUsernameProblemLanguageResultExecution timeMemory
227631bensonlzlPaths (BOI18_paths)C++14
100 / 100
656 ms172408 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll sum = 0, dp[2][300005][(1 << 5)]; vector<int> AdjList[300005]; int N, M, K, X, Y, colour[300005]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> N >> M >> K; for (int i = 1; i <= N; ++i){ cin >> colour[i]; colour[i]--; } for (int i = 1; i <= M; ++i){ cin >> X >> Y; AdjList[X].push_back(Y); AdjList[Y].push_back(X); } for (int i = 1; i <= N; ++i){ for (int mask = 0; mask < (1 << 5); ++mask){ dp[0][i][mask] = dp[1][i][mask] = 0; } dp[0][i][(1 << colour[i])] = 1; } for (int i = 1; i < K; ++i){ for (int v = 1; v <= N; ++v){ for (int mask = 0; mask < (1 << 5); ++mask){ dp[i&1][v][mask] = 0; if ((mask & (1 << colour[v])) == 0) continue; for (auto it : AdjList[v]){ dp[i&1][v][mask] += dp[(i-1)&1][it][mask ^ (1 << colour[v])]; } sum += dp[i&1][v][mask]; } } } cout << sum << '\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...