fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Edge { int to, id; };
  5.  
  6. int N, M, K;
  7. vector<vector<Edge>> g;
  8. vector<int> tin, low, isBridge;
  9. int timerDFS = 0;
  10.  
  11. void dfsBridge(int u, int pEdge) {
  12.     tin[u] = low[u] = ++timerDFS;
  13.     for (auto e : g[u]) {
  14.         if (e.id == pEdge) continue;
  15.         if (!tin[e.to]) {
  16.             dfsBridge(e.to, e.id);
  17.             low[u] = min(low[u], low[e.to]);
  18.             if (low[e.to] > tin[u]) isBridge[e.id] = 1;
  19.         } else {
  20.             low[u] = min(low[u], tin[e.to]);
  21.         }
  22.     }
  23. }
  24.  
  25. vector<int> comp;
  26. vector<int> compSize;
  27. void dfsComp(int u, int c) {
  28.     comp[u] = c;
  29.     compSize[c]++;
  30.     for (auto e : g[u]) if (comp[e.to] == -1 && !isBridge[e.id]) {
  31.         dfsComp(e.to, c);
  32.     }
  33. }
  34.  
  35. vector<vector<int>> tree;
  36. vector<int> subSize;
  37. vector<bool> removed;
  38. long long badPairs = 0;
  39.  
  40. int getSize(int u, int p) {
  41.     subSize[u] = compSize[u];
  42.     for (int v : tree[u]) if (v != p && !removed[v]) {
  43.         subSize[u] += getSize(v, u);
  44.     }
  45.     return subSize[u];
  46. }
  47.  
  48. int getCentroid(int u, int p, int n) {
  49.     for (int v : tree[u]) if (v != p && !removed[v]) {
  50.         if (subSize[v] > n/2) return getCentroid(v, u, n);
  51.     }
  52.     return u;
  53. }
  54.  
  55. void collect(int u, int p, int d, vector<pair<int,int>>& nodes) {
  56.     nodes.push_back({d, compSize[u]});
  57.     for (int v : tree[u]) if (v != p && !removed[v]) {
  58.         collect(v, u, d+1, nodes);
  59.     }
  60. }
  61.  
  62. void solveCentroid(int c) {
  63.     vector<long long> freq(1, 0);
  64.     freq[0] = compSize[c];
  65.  
  66.     for (int v : tree[c]) if (!removed[v]) {
  67.         vector<pair<int,int>> distSub;
  68.         collect(v, c, 1, distSub);
  69.         int maxd = 0;
  70.         for (auto [d,_] : distSub) maxd = max(maxd, d);
  71.         if ((int)freq.size() < maxd + K + 1) freq.resize(maxd + K + 1, 0);
  72.  
  73.         vector<long long> pref(freq.size(), 0);
  74.         for (int i=0; i<(int)freq.size(); i++) {
  75.             pref[i] = freq[i] + (i ? pref[i-1] : 0);
  76.         }
  77.  
  78.         for (auto [d, cnt] : distSub) {
  79.             int lim = K - d - 1;
  80.             if (lim >= 0) {
  81.                 lim = min(lim, (int)freq.size() - 1);
  82.                 long long s = pref[lim];
  83.                 badPairs += 1LL * cnt * s;
  84.             }
  85.         }
  86.  
  87.         for (auto [d, cnt] : distSub) freq[d] += cnt;
  88.     }
  89. }
  90.  
  91. void decompose(int u) {
  92.     int n = getSize(u, -1);
  93.     int c = getCentroid(u, -1, n);
  94.     solveCentroid(c);
  95.     removed[c] = true;
  96.     for (int v : tree[c]) if (!removed[v]) decompose(v);
  97. }
  98.  
  99. int main() {
  100.     ios::sync_with_stdio(false);
  101.     cin.tie(nullptr);
  102.  
  103.     cin >> N >> M >> K;
  104.     g.assign(N+1, {});
  105.     for (int i=1; i<=M; i++) {
  106.         int u,v; cin >> u >> v;
  107.         g[u].push_back({v,i});
  108.         g[v].push_back({u,i});
  109.     }
  110.  
  111.     tin.assign(N+1,0);
  112.     low.assign(N+1,0);
  113.     isBridge.assign(M+1,0);
  114.     for (int i=1; i<=N; i++) if (!tin[i]) dfsBridge(i,-1);
  115.  
  116.     comp.assign(N+1, -1);
  117.     int compCnt = 0;
  118.     for (int i=1; i<=N; i++) if (comp[i] == -1) {
  119.         compSize.push_back(0);
  120.         dfsComp(i, compCnt++);
  121.     }
  122.  
  123.     tree.assign(compCnt, {});
  124.     for (int u=1; u<=N; u++) {
  125.         for (auto e : g[u]) if (isBridge[e.id]) {
  126.             int cu = comp[u], cv = comp[e.to];
  127.             if (cu != cv) tree[cu].push_back(cv);
  128.         }
  129.     }
  130.  
  131.     subSize.assign(compCnt, 0);
  132.     removed.assign(compCnt, false);
  133.  
  134.     long long total = accumulate(compSize.begin(), compSize.end(), 0LL);
  135.     long long totalPairs = total * (total - 1) / 2;
  136.  
  137.     decompose(0);
  138.  
  139.     cout << totalPairs - badPairs << "\n";
  140. }
  141.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin 
8 9 2
1 5
1 5
2 3
2 6
3 7
4 8
5 6
6 7
7 8
stdout 
15
https://ideone.com/vIYnml
language:
C++14 (clang 8.0)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!