Advertisement
skimono

Untitled

Feb 23rd, 2023
706
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.10 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef unsigned long long ull;
  7. typedef long double ld;
  8. typedef string str;
  9. #define sqrt sqrtl
  10. #define F first
  11. #define S second
  12. #define endl '\n'
  13. #define all(vc666) vc666.begin(), vc666.end()
  14. #define allr(vc666) vc666.rbegin(), vc666.rend()
  15. #define int long long
  16.  
  17. const ll INF = (ll)1e18 + 7;
  18. const ll MOD = (ll)1e9 + 7;
  19. const ll ONE = 1;
  20. const ll max_sz = 1e5 + 1, max_sz2 = 101;
  21. ld EPS = 1e-7;
  22. ld PI = 3.1415926535897932384;
  23. mt19937_64 gen(time(0));
  24.  
  25. signed main() {
  26. #ifdef _DEBUG
  27.     freopen("input.txt", "r", stdin);
  28.     freopen("output.txt", "w", stdout);
  29. #endif
  30.     ios_base::sync_with_stdio(0);
  31.     cin.tie(NULL);
  32.     cout.tie(NULL);
  33.     int t = 1;
  34.     while (t--) {
  35.         int n, m, i, x, y, ans = 0;
  36.         cin >> n >> m;
  37.         vector<set<int> > g(n);
  38.         set<pair<int, int> > keys;
  39.         vector<pair<int, int> > a(n);
  40.         for (i = 0; i < n; i++) {
  41.             a[i].second = i;
  42.         }
  43.         for (i = 0; i < m; i++) {
  44.             cin >> x >> y;
  45.             x--;
  46.             y--;
  47.             a[x].first++;
  48.             a[y].first++;
  49.             g[x].insert(y);
  50.             g[y].insert(x);
  51.         }
  52.         sort(all(a));
  53.         vector<int> id(n);
  54.         for (i = 0; i < n; i++) {
  55.             id[a[i].second] = i;
  56.         }
  57.         vector<vector<int> > g2(n);
  58.         for (i = 0; i < n; i++) {
  59.             x = a[i].second;
  60.             for (auto u : g[x]) {
  61.                 if (id[u] > i) {
  62.                     g2[x].push_back(u);
  63.                 }
  64.             }
  65.         }
  66.         vector<int> cort(n);
  67.         for (i = 0; i < n - 2; i++) {
  68.             x = a[i].second;
  69.             for (auto u : g2[x]) {
  70.                 cort[id[u]]++;
  71.             }
  72.             for (auto u : g2[x]) {
  73.                 for (auto u2 : g2[u]) {
  74.                     if (cort[id[u2]]) {
  75.                         ans++;
  76.                     }
  77.                 }
  78.             }
  79.             for (auto u : g2[x]) {
  80.                 cort[id[u]]--;
  81.             }
  82.         }
  83.         cout << ans << endl;
  84.     }
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement