Advertisement
Guest User

Untitled

a guest
Apr 1st, 2024
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ve vector
  4. #define ll long long
  5. #define fi first
  6. #define se second
  7. #define all(x) x.begin(), x.end()
  8.  
  9. using namespace std;
  10.  
  11. const int MAXN = 100;
  12.  
  13. ve<int> g[MAXN];
  14. int dp0[MAXN];
  15. int dp1[MAXN][MAXN];
  16. int dp2[MAXN][MAXN][MAXN];
  17. bool dp3[MAXN][MAXN][MAXN][MAXN];
  18.  
  19. ll res = 0;
  20.  
  21. #pragma GCC optimize("Ofast")
  22.  
  23. void solve(){
  24.     int n, m;
  25.     cin >> n >> m;
  26.     for(int i = 0; i < m; i++){
  27.         int a, b;
  28.         cin >> a >> b;
  29.         a--; b--;
  30.         g[a].push_back(b);
  31.         g[b].push_back(a);
  32.     }
  33.     ve<int> prev;
  34.     for(int v = 0; v < n; v++){
  35.         for(auto a : g[v])
  36.             for(auto b : g[a]){
  37.                 if(b == v) continue;
  38.                 for(auto c : g[b]){
  39.                     if(c == v || c == a) continue;
  40.                     dp3[v][a][b][c] = 1;
  41.                     dp0[v]++;
  42.                     dp1[v][a]++;
  43.                     dp1[v][b]++;
  44.                     dp1[v][c]++;
  45.                     dp2[v][a][b]++;
  46.                     dp2[v][a][c]++;
  47.                     dp2[v][b][c]++;
  48.                 }
  49.             }
  50.     }
  51.     for(int v = 0; v < n; v++){
  52.         for(auto a : g[v])
  53.             for(auto b : g[a]){
  54.                 if(b == v) continue;
  55.                 for(auto c : g[b]){
  56.                     if(c == v || c == a) continue;
  57.                     int cans = dp0[v];
  58.                     cans -= dp1[v][a];
  59.                     cans -= dp1[v][b];
  60.                     cans -= dp1[v][c];
  61.                     cans += dp2[v][a][b];
  62.                     cans += dp2[v][b][a];
  63.                     cans += dp2[v][a][c];
  64.                     cans += dp2[v][c][a];
  65.                     cans += dp2[v][b][c];
  66.                     cans += dp2[v][c][b];
  67.                     cans -= dp3[v][a][b][c];
  68.                     cans -= dp3[v][a][c][b];
  69.                     cans -= dp3[v][b][a][c];
  70.                     cans -= dp3[v][b][c][a];
  71.                     cans -= dp3[v][c][a][b];
  72.                     cans -= dp3[v][c][b][a];
  73.                     res += cans;
  74.                 }
  75.             }
  76.     }
  77.     cout << res << "\n";
  78. }
  79. signed main(){
  80.     ios_base::sync_with_stdio(0);
  81.     int T = 1;
  82.     // cin >> T;
  83.    
  84.     while(T--){
  85.         solve();
  86.     }
  87. }
  88.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement