Madiyar

Untitled

Mar 24th, 2012
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <vector>
  8. #include <map>
  9. #include <set>
  10. #include <ctime>
  11. #include <cassert>
  12. #include <queue>
  13. using namespace std;
  14.  
  15. #define f first
  16. #define s second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
  20. #define f0(a) memset(a, 0, sizeof(a))
  21. #define all(v) v.begin(), v.end()
  22. #define pii pair<int,int>
  23. #define vi vector<int>
  24.  
  25. #ifdef WIN32
  26. #define I64 "%I64d"
  27. #else
  28. #define I64 "%lld"
  29. #endif
  30.  
  31. struct Cartesian {
  32.  
  33. struct Tree {
  34.  
  35. Tree *l, *r;
  36. int sz, y;
  37. bool rev;
  38.  
  39. Tree() {
  40. l = r = 0;
  41. sz = y = 0;
  42. rev = false;
  43. }
  44. };
  45.  
  46. int Count(Tree *v) {
  47. if (!v) return 0;
  48. return v -> sz;
  49. }
  50.  
  51. void norm(Tree *v) {
  52. if (!v) return;
  53. v -> sz = Count(v -> l) + Count(v -> r) + 1;
  54. }
  55.  
  56. void Push(Tree *v) {
  57.  
  58. if (!v) return;
  59.  
  60. if (!v -> rev) return;
  61.  
  62. swap(v -> l, v -> r);
  63. if (v -> l) v -> l -> rev ^= 1;
  64. if (v -> r) v -> r -> rev ^= 1;
  65. v -> rev = 0;
  66.  
  67. }
  68.  
  69.  
  70.  
  71. Tree *Merge(Tree *l, Tree *r) {
  72. if (!l) return r;
  73. if (!r) return l;
  74. Push(l); Push(r);
  75. if (l -> y > r -> y) {
  76. l -> r = Merge(l -> r, r);
  77. norm(l);
  78.  
  79. return l;
  80. } else {
  81. r -> l = Merge(l, r -> l);
  82. norm(r);
  83. return r;
  84. }
  85.  
  86. }
  87.  
  88.  
  89. void split(Tree *root, int x, Tree *&l, Tree *&r) {
  90. if (!root) {
  91. l = r = 0;
  92. return;
  93. }
  94.  
  95. if (Count(root->l) + 1 <= x) {
  96. Split(root -> r, x - Count(root -> l) - 1, root -> r, r);
  97. norm(root);
  98. } else {
  99. Split(root -> l, x, l, root -> l);
  100. norm(root);
  101. }
  102. }
  103.  
  104. };
  105.  
  106.  
  107. int main() {
  108. #ifdef LOCAL
  109. freopen("in", "r", stdin);
  110. freopen("out", "w", stdout);
  111. #endif
  112. while (true) {
  113. scanf("%d%d%d%d", &n, &m, &c, &t);
  114. if (n == 0) break;
  115.  
  116. for (int i = 0; i < m; ++i) {
  117. int u, v, k;
  118. scanf("%d%d%d", &u, &v, &k);
  119. g[k][u].pb(v);
  120. g[k][v].pb(u);
  121. Map[mp(u,v)] = Map[mp(v, u)] = k;
  122. }
  123.  
  124.  
  125. for (int i = 1; i <= n; ++i)
  126. used[i] = 0;
  127.  
  128. for (int col = 1; col <= c; ++col) {
  129.  
  130. for (int i = 1;i <= n; ++i)
  131. if (g[col][i].size() == 1) {
  132.  
  133. Tn++;
  134.  
  135. int v = i;
  136.  
  137.  
  138. while (true) {
  139. T[Tn - 1].add(v);
  140. used[v] = col;
  141.  
  142. bool found = false;
  143.  
  144. forit(it,g[col][v]) {
  145. if (used[*it] != col) {v = *it; found = true; break;}
  146. }
  147.  
  148. if (!found) break;
  149. }
  150. }
  151. }
  152.  
  153. for (int it = 0; it < t; ++it) {
  154. int u, v, k;
  155. scanf("%d%d%d", &u, &v, &k);
  156.  
  157. if (!Map.count(mp(u,v))) {
  158. puts("No such cable.");
  159. continue;
  160. }
  161.  
  162. int col = Map[mp(u,v)];
  163.  
  164. if (col == k) {
  165. puts("Already owned.");
  166. continue;
  167. }
  168.  
  169. if (deg[k][u] == 2 || deg[k][v] == 2) {
  170. puts("Forbidden: monopoly.");
  171. continue;
  172. }
  173.  
  174. if (next[k][u] == v) {
  175. puts("Forbidden: redundanet.");
  176. continue;
  177. }
  178.  
  179. puts("Sold.");
  180.  
  181.  
  182. }
  183.  
  184. }
  185. return 0;
  186.  
  187. }
Advertisement
Add Comment
Please, Sign In to add comment