Submission #864357

#TimeUsernameProblemLanguageResultExecution timeMemory
864357maks007Paths (BOI18_paths)C++14
70 / 100
453 ms42148 KiB
#include "bits/stdc++.h" using namespace std; #define int long long vector <int> color; vector <vector <int>> cntColor, g, dp; signed main () { int n, m, k; cin >> n >> m >> k; color.resize(n); cntColor.resize(n, vector <int> (k + 1, 0)); g.resize(n); for(int i = 0; i < n; i ++) cin >> color[i]; for(int i = 0, u, v; i < m; i ++) { cin >> u >> v; u --, v --; g[u].push_back(v); g[v].push_back(u); cntColor[u][color[v]] ++; cntColor[v][color[u]] ++; } int ans = 0; for(int color2 = 1; color2 <= k; color2 ++) { for(int i = 0; i < n; i ++) { if(color[i] == color2) { for(int color1 = 1; color1 <= k; color1 ++) { if(color1 == color2) continue; ans += cntColor[i][color1]; if(k == 2) continue; for(int color3 = color1 + 1; color3 <= k; color3 ++) { if(color3 == color2) continue; ans += 2 * (cntColor[i][color1] * cntColor[i][color3]); } } } } } if(k >= 4) { for(int v = 0; v < n; v ++) { for(auto u : g[v]) { if(color[u] == color[v]) continue; for(int i = 1; i <= k; i ++) { if(i == color[u] || color[v] == i) continue; for(int j = 1; j <= k; j ++) { if(j == i || j == color[u] || j == color[v]) continue; ans += cntColor[v][i] * cntColor[u][j]; } } } } } if(k >= 5) { dp.resize(n, vector <int> (1 << (k + 1))); for(int i = 0; i < n; i ++) { for(int color1 = 1; color1 <= k; color1 ++) { for(int color2 = color1 + 1; color2 <= k; color2 ++) { int cnt = 0; for(auto u : g[i]) { if(color[u] == color1 || color[u] == color2) cnt ++; } dp[i][(1 << color1) ^ (1 << color2)] = cnt; } } } /*for(int mid = 0; mid < n; mid ++) { for(auto l : g[mid]) { if(color[mid] == color[l]) continue; for(auto r : g[mid]) { if(color[mid] == color[r] || color[l] == color[r]) continue; int bitVal = ((1 << (k + 1)) - 1) ^ (1 << mid) ^ (1 << l) ^ (1 << r); ans += dp[l][bitVal] * dp[r][bitVal]; } } }*/ } cout << ans; 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...