fork download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <algorithm>
  4. using namespace std;
  5. #define maxn 5555
  6.  
  7. int n, m, i, j, c[maxn], x[maxn], y[maxn], bad, it, k, used[maxn], gx[maxn], a[maxn][maxn], match[maxn], forbidden, de[maxn], tot, color[maxn];
  8. bool wrong[maxn][maxn];
  9. long long res;
  10. int graph(int x){
  11. 	return (x*(x-1))/2;
  12. }
  13. int main(){
  14. 	freopen("input.txt", "r", stdin);
  15. 	freopen("output.txt", "w", stdout);
  16. 	scanf("%d %d", &n, &m);
  17. 	for(i = 1; i<=m; i++){
  18. 		scanf("%d %d", &x[i], &y[i]);
  19. 		if (x[i]>y[i]) swap(x[i], y[i]);
  20. 		wrong[x[i]][y[i]] = 1;
  21. 		a[x[i]][++c[x[i]]] = y[i];
  22. 	}
  23. 	for(i = 1; i<=n; i++){
  24. 		gx[i] = 0;
  25. 		for(j = 1; j<=m; j++) if (x[j]>i) ++gx[i];                                                                
  26. 	}
  27. 	res = n+graph(n)-m;
  28. 	for(i = 1; i<=n; i++){
  29. 		forbidden = c[i];		
  30. 		for(j = i+1; j<=n; j++) if (!wrong[i][j]){
  31. 			match[j] = n - j - c[j] - forbidden;
  32. 			for(k = 1; k<=c[j]; k++) if (wrong[i][a[j][k]]) ++match[j];
  33. 			res += match[j];
  34. 		}else --forbidden;
  35. 		for(j = 1; j<=n; j++) de[j] = 0;
  36. 		for(j = 1; j<=c[i]; j++) de[a[i][j]]=1; tot = c[i];
  37. 		for(j = 1; j<i; j++) if (!wrong[j][i]){
  38. 			for(k = 1; k<=c[j]; k++){
  39. 				++de[a[j][k]];
  40. 				if (de[a[j][k]]==1 && a[j][k]>i) ++tot;
  41. 			}
  42. 			res += graph(n-i-tot);
  43. 			for(k = 1; k<=c[j]; k++){
  44. 				--de[a[j][k]];
  45. 				if (de[a[j][k]]==0 && a[j][k]>i) --tot;
  46. 			}
  47. 		}
  48. 	}
  49. 	for(i = 1; i<=m; i++){
  50. 		for(j = 1; j<=n; j++) color[j] = 1;
  51. 		tot = 0;
  52. 		for(j = 1; j<x[i]; j++) if ((wrong[j][x[i]]||wrong[j][y[i]])==0){
  53. 			color[j] = 0;
  54. 			++tot;
  55. 		}
  56. 		res -= graph(tot);
  57. 		for(j = 1; j<=m; j++) if (y[j]<x[i] && color[x[j]]+color[y[j]]==0) ++res;
  58. 	}
  59. 	cout << res << endl;
  60. 	return 0;
  61. }
  62.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2qWPO
language:
C++ (gcc 8.3)
created:
12 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!