Advertisement
Guest User

Untitled

a guest
Apr 27th, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.32 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <fstream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <map>
  7. using namespace std;
  8.  
  9. ifstream fin("input.txt");
  10. ofstream fout("output.txt");
  11. int H, V, vertexnum = 0, Wprice, Kprice = 0;
  12. vector<int> p, rang;
  13. vector <pair<int, pair<int, int>>> g;
  14.  
  15. struct Word
  16. {
  17. int r;
  18. int c1;
  19. int c2;
  20. vector<int> intersec;
  21. int cost;
  22. };
  23.  
  24. vector<Word> hor, ver;
  25.  
  26. void create_vector(vector<Word> &vec1, vector<Word> &vec2) {
  27. fin >> H >> V;
  28. for (int i = 0; i < H; ++i) {
  29. Word temp;
  30. int a, b, c;
  31. fin >> a >> b >> c; // r c1 c2 1 0 5
  32.  
  33. // r c1 c2 4 0 5
  34. temp.r = a;
  35. temp.c1 = min(b, c);
  36. temp.c2 = max(b, c);
  37. temp.cost = temp.c2 - temp.c1 + 1;
  38. temp.intersec.resize(0);
  39.  
  40. vec1.emplace_back(temp);
  41. }
  42. for (int i = 0; i < V; ++i) {
  43. Word temp;
  44. int a, b, c;
  45. fin >> a >> b >> c; // r1 r2 c 0 5 1
  46.  
  47. // r1 r2 c 0 5 3
  48. temp.r = c; // r <- c
  49. temp.c1 = a; // c1 <- r1
  50. temp.c2 = b; // c2 <- r2
  51. temp.cost = abs(b - a + 1);
  52. temp.intersec.resize(0);
  53.  
  54. vec2.emplace_back(temp);
  55. }
  56.  
  57. }
  58.  
  59. int count_cost(vector<Word> &vec1, vector<Word> &vec2) {
  60. int a = 0;
  61. for (int i = 0; i < vec1.size(); ++i) {
  62. a += vec1[i].cost;
  63. }
  64. for (int i = 0; i < vec2.size(); ++i) {
  65. a += vec2[i].cost;
  66. }
  67. return a;
  68. }
  69.  
  70. void sort_words(vector<Word> &vec1) {
  71. sort(vec1.begin(), vec1.end(), [](const Word &v1, const Word &v2) -> bool {
  72. int r1 = v1.c1;
  73. int r2 = v2.c1;
  74. return r1 < r2;
  75. });
  76. }
  77.  
  78.  
  79. void sort_intersec(vector<Word> &h, vector<Word> &v) {
  80. for (int i = 0; i < h.size(); ++i)
  81. sort(h[i].intersec.begin(), h[i].intersec.end());
  82.  
  83. for (int i = 0; i < v.size(); ++i)
  84. sort(v[i].intersec.begin(), v[i].intersec.end());
  85. }
  86. void find_intersections(vector<Word> &h, vector<Word> &v, const int N1, const int N2, int &cnt)
  87. {
  88. for (int i = 0; i < N1; ++i)
  89. for (int j = 0; j < N2; ++j) {
  90. if (v[j].c1 <= h[i].r && h[i].r <= v[j].c2 && h[i].c1 <= v[j].r && v[j].r <= h[i].c2) {
  91. h[i].intersec.emplace_back(v[j].r);
  92. v[j].intersec.emplace_back(h[i].r);
  93. cnt += 1;
  94. }
  95. }
  96.  
  97.  
  98. }
  99.  
  100. void create_graph(vector<Word> &h, vector<Word> &v, vector <pair<int, pair<int, int>>> &adjG)
  101. {
  102. map<pair<int, int>, int> iss;
  103.  
  104. int a = 0, b = 0;
  105. for (int i = 0; i < h.size(); ++i) {
  106. if (h[i].intersec.size() > 1) {
  107. a = b++;
  108. for (int j = 0; j < h[i].intersec.size() - 1; ++j) {
  109. a = b;
  110. b++;
  111. pair<int, pair<int, int>> p;
  112.  
  113. p.second.first = a;
  114. p.second.second = b;
  115. ///
  116. iss.emplace(make_pair(make_pair(h[i].r, h[i].intersec[j]), a));
  117. //cout << a << ':' << h[i].r << ' ' << h[i].intersec[j] << endl;
  118. iss.emplace(make_pair(make_pair(h[i].r, h[i].intersec[j + 1]), b));
  119. //cout << b << ':' << h[i].r << ' ' << h[i].intersec[j + 1] << endl;
  120. ///
  121. p.first = abs(h[i].intersec[j + 1] - h[i].intersec[j] - 1);
  122. //cout << a << ' ' << b << ' ' << p.first << endl;
  123. adjG.emplace_back(p);
  124. }
  125. }
  126. ///
  127. else if (h[i].intersec.size() == 1) {
  128. iss.emplace(make_pair(make_pair(h[i].r, h[i].intersec[0]), b));
  129. //cout << b << ':' << h[i].r << ' ' << h[i].intersec[0] << endl;
  130. a = b;
  131. b++;
  132. }
  133. ///
  134. }
  135.  
  136. for (int i = 0; i < v.size(); ++i) {
  137. if (v[i].intersec.size() > 0)
  138. for (int j = 0; j < v[i].intersec.size() - 1; ++j) {
  139. pair<int, pair<int, int>> p;
  140. ///
  141. p.second.first = iss[make_pair(v[i].intersec[j], v[i].r)];
  142. p.second.second = iss[make_pair(v[i].intersec[j + 1], v[i].r)];
  143. ///
  144. p.first = abs(v[i].intersec[j + 1] - v[i].intersec[j] - 1);
  145. //cout << p.second.first << ' ' << p.second.second << ' ' << p.first << endl;
  146. adjG.emplace_back(p);
  147. }
  148.  
  149. }
  150. //cout << "-----" << endl;
  151.  
  152. }
  153. int dsu_get(int v) {
  154. if (v == p[v])
  155. return v;
  156. return p[v] = dsu_get(p[v]);
  157. }
  158.  
  159. void dsu_unite(int a, int b) {
  160. int ra = dsu_get(a);
  161. int rb = dsu_get(b);
  162. if (ra == rb)
  163. return;
  164. if (rang[ra] > rang[rb])
  165. swap(ra, rb);
  166. p[ra] = rb;
  167. if (rang[ra] == rang[rb])
  168. rang[rb]++;
  169.  
  170. }
  171.  
  172. void kruskal(vector <pair<int, pair<int, int>>> &adjG, const int cnt, int &c)
  173. {
  174. int cost = 0, n = cnt, m = adjG.size();
  175. sort(g.begin(), g.end(), [](auto& t1, auto& t2) {
  176. return (t1.first < t2.first);
  177. });
  178. //for (auto& t : g)
  179. // cout << t.first << ' ' << t.second.first << ' ' << t.second.second << endl;
  180. p.resize(1001 * n);
  181. rang.resize(1001 * n, 0);
  182.  
  183. for (int i = 0; i < 1001 * n; ++i)
  184. p[i] = i;
  185.  
  186. for (int i = 0; i < m; ++i) {
  187. int a = g[i].second.first, b = g[i].second.second, l = g[i].first;
  188. if (dsu_get(a) == dsu_get(b)) {
  189. if (l == 0) {
  190. fout << -1 << endl;
  191. fout.close();
  192. return;
  193. }
  194. }
  195. else {
  196. //cout << a << ' ' << b << endl;
  197. dsu_unite(a, b);
  198. cost += l;
  199. continue;
  200. }
  201. }
  202. c = cost;
  203. }
  204.  
  205. void print_result(int Wp, int Kp, int vernum) {
  206. fout << Wp + Kp + vernum << endl;
  207. fout.close();
  208. }
  209. int main() {
  210.  
  211. create_vector(hor, ver);
  212.  
  213. Wprice = count_cost(hor, ver);
  214.  
  215. sort_words(hor);
  216.  
  217. sort_words(ver);
  218.  
  219. find_intersections(hor, ver, H, V, vertexnum);
  220.  
  221. sort_intersec(hor, ver);
  222.  
  223. create_graph(hor, ver, g);
  224.  
  225. kruskal(g, vertexnum, Kprice);
  226. int rest = 0;
  227. for (auto& t : hor) {
  228. if (t.intersec.size() == 0)
  229. rest += t.c2 - t.c1 + 1;
  230. else
  231. rest += *t.intersec.begin() - t.c1 + t.c2 - *t.intersec.rbegin();
  232. }
  233. for (auto& t : ver) {
  234. if (t.intersec.size() == 0)
  235. rest += t.c2 - t.c1 + 1;
  236. else
  237. rest += *t.intersec.begin() - t.c1 + t.c2 - *t.intersec.rbegin();
  238. }
  239. //cout << rest << ' ' << vertexnum << ' ' << Kprice << endl;
  240.  
  241. print_result(rest, Kprice, vertexnum);
  242.  
  243. return EXIT_SUCCESS;
  244. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement