Advertisement
Korotkodul

Электрички топсорт додебажить

Jan 18th, 2022 (edited)
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.49 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int,int>
  11. #define vec vector
  12. using namespace std;
  13. using ll = long long;
  14. using ld = long double;
  15. using db = double;
  16. void cv(vector <int> &v){
  17. for (auto x: v) cout<<x<<' ';
  18. cout<<"\n";
  19. }
  20.  
  21. void cvl(vector <ll> &v){
  22. for (auto x: v) cout<<x<<' ';
  23. cout<<"\n";
  24. }
  25.  
  26.  
  27. void cvv(vector <vector <int> > &v){
  28. for (auto x: v) cv(x);
  29. cout<<"\n";
  30. }
  31. int n;
  32. struct el{
  33. int a,b, c,d;
  34. };
  35.  
  36. void mk(el &x){
  37. cin>>x.a>>x.b>>x.c>>x.d;
  38. }
  39.  
  40. int tm(el x, int p){
  41. return x.c + x.d * (p - x.a);
  42. }
  43.  
  44. int inter(el x, el y){
  45. if (y.b >= x.a && y.a < x.a){
  46. //p = min(x.b, y.b);
  47. return 1;
  48. }
  49. if (y.a <= x.b && y.b > x.b){
  50. //p = max(x.a, y.a);
  51. return 2;
  52. }
  53. return 0;
  54. }
  55.  
  56.  
  57. vector <el> v;
  58. vector <vector <int> > G;
  59. void mkG(){
  60. el x,y;
  61. int p;
  62. G.resize(n);
  63. for (int i = 0; i < n;++i){
  64. x = v[i];
  65. for (int j = 0; j < n && j != i ; ++ j){
  66. p = -1;
  67. y = v[j];
  68. if (inter(x,y) == 1){
  69. p = min(x.b, y.b);
  70. if (tm(x,p) == tm(y,p)){
  71. p--;
  72. }
  73. if (p < x.a || p < y.a){
  74. p = -1;
  75. }
  76. }
  77. else if (inter(x,y) == 2){
  78. p = max(x.a, y.a);
  79. if (tm(x,p) == tm(y,p)){
  80. p++;
  81. }
  82. if (p > x.b || p > y.b) {
  83. p=-1;
  84. }
  85. }
  86. if (p != -1){
  87. if (tm(x,p) < tm(y,p)){
  88. G[i].push_back(j);
  89. }
  90. else if (tm(x,p) > tm(y,p)){
  91. G[j].push_back(i);
  92. }
  93. }
  94. }
  95. }
  96. }
  97. const int wh=0, gr=1, bl=2;
  98. vector <int> clr;
  99. vector <int> ans;
  100.  
  101. void dfs(int v) {
  102. clr[v] = gr;
  103. for (int u: G[v]){
  104. if (clr[u] == wh){
  105. dfs(u);
  106. }
  107. }
  108. clr[v] = bl;
  109. ans.push_back(v+1);
  110. }
  111.  
  112. int main()
  113. {
  114. ios::sync_with_stdio(0);
  115. cin.tie(0);
  116. cout.tie(0);
  117. cin>>n;
  118. v.resize(n);
  119. for (int i=0;i<n;++i) mk(v[i]);
  120. mkG();
  121. clr.assign(n, wh);
  122. for (int i = 0; i < n;++i){
  123. if (clr[i] == wh) dfs(i);
  124. }
  125. reverse(ans.begin(), ans.end());
  126. cv(ans);
  127. }
  128. /*
  129. 3
  130. 1 10 3 4
  131. 3 5 3 4
  132. 10 11 10 1
  133. */
  134.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement