Submission #1111699

#TimeUsernameProblemLanguageResultExecution timeMemory
1111699PagodePaivaPaths (BOI18_paths)C++17
70 / 100
331 ms39380 KiB
#include<bits/stdc++.h> #define int long long using namespace std; const int N = 300010; int n,m, k; vector <int> g[N]; int cor[N]; int res = 0; int dp[N][6]; void solve(int x){ if(x == 2){ int t = 0; for(int i = 1;i <= n;i++){ for(auto x : g[i]){ if(cor[x] != cor[i]) t++; } } res += t; return; } if(x == 3){ for(int v = 1;v <= n;v++){ int resp = 0; for(auto x : g[v]){ if(cor[x] == cor[v]) continue; for(int j = 1;j <= k;j++){ if(j == cor[x] or j == cor[v]) continue; resp += dp[v][j]; } } res += resp; } return; } if(x == 4){ for(int v = 1;v <= n;v++){ int resp = 0; for(auto x : g[v]){ if(cor[x] == cor[v]) continue; for(int j = 1;j <= k;j++){ if(cor[x] == j or cor[v] == j) continue; for(int t = 1;t <= k;t++){ if(cor[x] == t or cor[v] == t or j == t) continue; resp += dp[v][j]*dp[x][t]; } } } res += resp; } } } int32_t main(){ cin >> n >> m >> k; for(int i = 1;i <= n;i++){ cin >> cor[i]; } for(int i = 0;i < m;i++){ int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } for(int i = 1;i <= n;i++){ int v = i; for(auto x : g[v]){ dp[v][cor[x]]++; } } for(int i = 2;i <= k;i++){ solve(i); } cout << res << '\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...