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 goodPairs=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.  
  55.     for(int v:tree[c]) if(!removed[v]){
  56.         vector<pair<int,int>> distSub;
  57.         collect(v,c,1,distSub);
  58.         int maxd=0;
  59.         for(auto [d,_]:distSub) maxd=max(maxd,d);
  60.         if((int)freq.size() < maxd+K+1) freq.resize(maxd+K+1,0);
  61.  
  62.         vector<long long> suff(freq.size()+1,0);
  63.         for(int i=(int)freq.size()-1;i>=0;i--){
  64.             suff[i] = freq[i] + suff[i+1];
  65.         }
  66.  
  67.         for(auto [d,cnt]:distSub){
  68.             int lim = K-d;
  69.             if(lim<0) lim=0;
  70.             if(lim < (int)freq.size()){
  71.                 long long s = suff[lim];
  72.                 goodPairs += 1LL * cnt * s;
  73.             }
  74.         }
  75.  
  76.         for(auto [d,cnt]:distSub) freq[d]+=cnt;
  77.     }
  78. }
  79.  
  80. void decompose(int u){
  81.     int n=getSize(u,-1);
  82.     int c=getCentroid(u,-1,n);
  83.     solveCentroid(c);
  84.     removed[c]=true;
  85.     for(int v:tree[c]) if(!removed[v]) decompose(v);
  86. }
  87.  
  88. int main(){
  89.     ios::sync_with_stdio(false);
  90.     cin.tie(nullptr);
  91.  
  92.     cin>>N>>M>>K;
  93.     g.assign(N+1,{});
  94.     for(int i=1;i<=M;i++){
  95.         int u,v; cin>>u>>v;
  96.         g[u].push_back({v,i});
  97.         g[v].push_back({u,i});
  98.     }
  99.  
  100.     tin.assign(N+1,0); low.assign(N+1,0); isBridge.assign(M+1,0);
  101.     for(int i=1;i<=N;i++) if(!tin[i]) dfsBridge(i,-1);
  102.  
  103.     comp.assign(N+1,-1);
  104.     int compCnt=0;
  105.     for(int i=1;i<=N;i++) if(comp[i]==-1){ compSize.push_back(0); dfsComp(i,compCnt++); }
  106.  
  107.     tree.assign(compCnt,{});
  108.     for(int u=1;u<=N;u++) for(auto e:g[u]) if(isBridge[e.id]){
  109.         int cu=comp[u], cv=comp[e.to];
  110.         if(cu!=cv) tree[cu].push_back(cv);
  111.     }
  112.  
  113.     subSize.assign(compCnt,0);
  114.     removed.assign(compCnt,false);
  115.  
  116.     decompose(0);
  117.  
  118.     cout<<goodPairs<<"\n";
  119. }
  120.  
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 
8
https://ideone.com/ompO6H
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!