fork download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <functional>
  4. #include <vector>
  5. #include <queue>
  6. using namespace std;
  7.  
  8. vector<pair<int, int> > make_tree(int n, vector<int> seq)
  9. {
  10. 	if (n <= 1) return vector<pair<int, int> >();
  11.  
  12. 	vector<int> deg(n + 1);
  13. 	for (int i = 0; i < n - 2; i++) deg[seq[i]]++;
  14. 	priority_queue<int, vector<int>, greater<int> > Q;
  15. 	vector<pair<int, int> > res;
  16. 	for (int i = 1; i <= n; i++) if (deg[i] == 0) Q.push(i);
  17. 	for (int i = 0; i < n - 2; i++) {
  18. 		int x = Q.top(), y = seq[i]; Q.pop();
  19. 		deg[x]--;
  20. 		if (--deg[y] == 0) Q.push(y);
  21. 		res.push_back(make_pair(x, y));
  22. 	}
  23.  
  24. 	int x, y;
  25. 	for (int i = 1; i <= n; i++) if (deg[i] == 0) { x = i; break; }
  26. 	for (int i = n; i >= 1; i--) if (deg[i] == 0) { y = i; break; }
  27. 	res.push_back(make_pair(x, y));
  28. 	return res;
  29. }
  30.  
  31. const int n = 4, d = 3;
  32. vector<int> g[n + 1];
  33. long long cnt = 0;
  34.  
  35. void go2(int x, int l, vector<int> &v)
  36. {
  37. 	if (l) {
  38. 		for (int i = 1; i < v.size(); i++) {
  39. 			{
  40. 				auto w = v;
  41. 				reverse(w.begin() + i, w.end());
  42. 				for (int j = i; j < w.size(); j++) w[j] += v[i - 1];
  43. 				if (is_sorted(w.begin(), w.end()) || is_sorted(w.rbegin(), w.rend())) cnt++;
  44. 			}
  45. 			{
  46. 				auto w = v;
  47. 				for (int j = i; j < w.size(); j++) w[j] = -w[j];
  48. 				for (int j = i; j < w.size(); j++) w[j] += v[i - 1];
  49. 				if (is_sorted(w.begin(), w.end()) || is_sorted(w.rbegin(), w.rend())) cnt++;
  50. 			}
  51. 		}
  52. 	}
  53. 	for (auto &y : g[x]) if (y != l) {
  54. 		v.push_back(y);
  55. 		go2(y, x, v);
  56. 		v.pop_back();
  57. 	}
  58. }
  59.  
  60. void go(int a, vector<int> &s)
  61. {
  62. 	if (a == s.size()) {
  63. 		auto t = make_tree(n, s);
  64.  
  65. 		for (int i = 1; i <= n; i++) g[i].clear();
  66. 		for (auto &p : t) {
  67. 			g[p.first].push_back(p.second);
  68. 			g[p.second].push_back(p.first);
  69. 		}
  70. 		bool r = 1;
  71. 		for (int i = 1; i <= n; i++) if (g[i].size() > d) r = 0;
  72.  
  73. 		if (r) for (int i = 1; i <= n; i++) {
  74. 			vector<int> v;
  75. 			v.push_back(i);
  76. 			go2(i, 0, v);
  77. 		}
  78. 	}
  79. 	else {
  80. 		for (int i = 1; i <= n; i++) {
  81. 			s[a] = i;
  82. 			go(a + 1, s);
  83. 		}
  84. 	}
  85. }
  86.  
  87. int main()
  88. {
  89. 	vector<int> s(n - 2);
  90. 	go(0, s);
  91. 	printf("%lld\n", cnt);
  92. 	return 0;
  93. }
Success #stdin #stdout 0s 4252KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
364
https://ideone.com/UxXm4A
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!