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