fork download
  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
stdin
Standard input is empty
stdout
364