fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i,a,b) for(int i=a;i<b;i++)
  4. #define REP(i,b) FOR(i,0,b)
  5. #define PB push_back
  6. #define MP make_pair
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11. typedef pair<int,int> pii;
  12.  
  13. int read(){
  14. 	int i;
  15. 	scanf("%d",&i);
  16. 	return i;
  17. }
  18.  
  19. const int maxN=100000;
  20. const int maxM=100000;
  21.  
  22. struct Edge{
  23. 	int to,weight,idx;
  24. 	bool operator<(const Edge& rhs)const{
  25. 		if(weight!=rhs.weight)
  26. 			return weight<rhs.weight;
  27. 		return to<rhs.to;
  28. 	}
  29. };
  30. vector<Edge> g1[maxN],g2[maxN];
  31. pii ord[maxN];
  32.  
  33. ll e2[maxM][2],v2[maxN];
  34. ll eTri[maxM],e3[maxM][2],v3[maxN];
  35. ll vQuad[maxN],v4[maxN];
  36. ll s[maxN];
  37. bool nb[maxN];
  38.  
  39. int main(){
  40. 	int n=read(),m=read();
  41. 	REP(i,m){
  42. 		int a=read()-1,b=read()-1;
  43. 		g1[a].PB(Edge{b,0,i});
  44. 		g1[b].PB(Edge{a,0,i});
  45. 		g2[a].PB(Edge{b,0,i});
  46. 		g2[b].PB(Edge{a,0,i});
  47. 	}
  48. 	REP(i,n){
  49. 		for(auto& e:g1[i])
  50. 			e.weight=g1[e.to].size();
  51. 		sort(g1[i].begin(),g1[i].end());
  52. 	}
  53. 	REP(i,n)
  54. 		ord[i]=MP((int)g1[i].size(),i);
  55. 	sort(ord,ord+n);
  56. 	for(int _i=n-1;_i>=0;_i--){
  57. 		int i=ord[_i].second;
  58. 		for(auto&& j:g1[i]){
  59. 			g1[j.to].resize(g1[j.to].size()-1);
  60. 			nb[j.to]=true;
  61. 			for(auto&& k:g1[j.to])
  62. 				s[k.to]=0;
  63. 		}
  64. 		for(auto&& j:g1[i])
  65. 			for(auto&& k:g1[j.to])
  66. 				s[k.to]++;
  67. 		for(auto&& j:g1[i])
  68. 			for(auto&& k:g1[j.to]){
  69. 				vQuad[i]+=s[k.to]-1;
  70. 				vQuad[j.to]+=(s[k.to]-1)*2;
  71. 				vQuad[k.to]+=s[k.to]-1;
  72. 				if(nb[k.to]){
  73. 					eTri[j.idx]+=2;
  74. 					eTri[k.idx]++;
  75. 				}
  76. 			}
  77. 		for(auto&& j:g1[i])
  78. 			nb[j.to]=false;
  79. 	}
  80. 	REP(i,m)
  81. 		eTri[i]/=2;
  82. 	REP(i,n)
  83. 		vQuad[i]/=2;
  84. 	REP(i,n)
  85. 		for(auto&& e:g2[i])
  86. 			v2[i]+=e2[e.idx][i<e.to]=g2[e.to].size()-1;
  87. 	REP(i,n)
  88. 		for(auto&& e:g2[i])
  89. 			v3[i]+=e3[e.idx][i<e.to]=v2[e.to]-e2[e.idx][e.to<i]-eTri[e.idx];
  90. 	REP(i,n){
  91. 		for(auto&& e:g2[i])
  92. 			v4[i]+=v3[e.to]-e3[e.idx][e.to<i]-eTri[e.idx]*(g2[i].size()-2);
  93. 		printf("%lld\n",v4[i]-vQuad[i]*2);
  94. 	}
  95. }
Runtime error #stdin #stdout 0s 14496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mN2eGf
language:
C++14 (gcc 8.3)
created:
9 years 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!