Submission #563666

#TimeUsernameProblemLanguageResultExecution timeMemory
563666colossal_pepePaths (BOI18_paths)C++17
20 / 100
409 ms315660 KiB
#include <iostream> #include <vector> using namespace std; using ll = long long; int n, m, k, c[300005]; ll dp[300005][5][5][5]; vector<vector<int>> g; ll solve() { ll ans = 0; if (k < 2) return ans; for (int u = 0; u < n; u++) { for (int v : g[u]) { dp[u][c[v]][0][0]++; } for (int x = 1; x <= k; x++) { if (x == c[u]) continue; ans += dp[u][x][0][0]; } } if (k < 3) return ans; for (int u = 0; u < n; u++) { for (int v : g[u]) { for (int x = 1; x <= k; x++) { dp[u][c[v]][x][0] += dp[v][x][0][0]; } } for (int x = 1; x <= k; x++) { if (x == c[u]) continue; for (int y = 1; y <= k; y++) { if (y == c[u] or y == x) continue; ans += dp[u][x][y][0]; } } } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> k; g.resize(n); for (int i = 0; i < n; i++) { cin >> c[i]; } while (m--) { int u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } cout << solve() << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...