Advertisement
Guest User

Untitled

a guest
Jan 17th, 2018
418
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.30 KB | None | 0 0
  1. /*
  2.  ID: bradyawn
  3.  PROG: contest
  4.  LANG: C++11
  5.  */
  6.  
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <iomanip>
  10. #include <fstream>
  11. #include <vector>
  12. #include <deque>
  13. #include <string>
  14. #include <cmath>
  15. #include <map>
  16. #include <utility>
  17. #include <algorithm>
  18. #include <set>
  19. #include <ctime>
  20. #include <queue>
  21. #include <stack>
  22. #include <bitset>
  23. #include <random>
  24. #include <cstring>
  25.  
  26. using namespace std;
  27.  
  28. typedef long long ll;
  29. typedef pair<int,int> i2;
  30. typedef pair<ll,ll> ll2;
  31.  
  32. int par[2001*2001+1];
  33. int r[2001*2001+1];
  34.  
  35. int find(int x)
  36. {
  37.     if (par[x] == x) return x;
  38.     return par[x] = find(par[x]);
  39. }
  40.  
  41. void merge(int x, int y) //merge set x under y
  42. {
  43.     int setX = find(x);
  44.     int setY = find(y);
  45.    
  46.     if (r[setX] == r[setY])
  47.     {
  48.         par[setX] = setY;
  49.         r[setY]++;
  50.     }
  51.     else if (r[setX] < r[setY]) par[setX] = setY;
  52.     else par[setY] = setX;
  53. }
  54.  
  55. int a, b, n, m;
  56.  
  57. int main()
  58. {
  59.     ifstream inf("fencedin.in");
  60.     ofstream outf("fencedin.out");
  61.     //outf << setprecision(10);
  62.     //ios_base::sync_with_stdio(0);
  63.     //inf.tie(0);
  64.    
  65.     inf >> a >> b >> n >> m;
  66.    
  67.     vector<int> v(n);
  68.     vector<int> h(m);
  69.    
  70.     for (int i = 0; i < n; i++) inf >> v[i];
  71.     for (int i = 0; i < m; i++) inf >> h[i];
  72.    
  73.     //Makes easier to parse
  74.     h.push_back(0);
  75.     h.push_back(b);
  76.    
  77.     v.push_back(0);
  78.     v.push_back(a);
  79.    
  80.     stable_sort(v.begin(), v.end());
  81.     stable_sort(h.begin(), h.end());
  82.    
  83.     //for (int i = 0; i < n; i++) outf << v[i] << " \n"[i==n-1];
  84.     //for (int i = 0; i < m; i++) outf << h[i] << " \n"[i==m-1];
  85.    
  86.     int total = (n+1)*(m+1);
  87.    
  88.     vector<pair<int, i2>> edges; //{len,{st,ed}}
  89.    
  90.     for (int i = 1; i <= m+1; i++) //below horizontal lines
  91.     {
  92.         int st = (i-1)*(n+1);
  93.         int vert = h[i]-h[i-1];
  94.        
  95.         for (int j = 1; j <= n; j++) //vertical
  96.         {
  97.             int leftH = v[j]-v[j-1]; //horizontal wall
  98.             int rightH = v[j+1]-v[j]; //horizontal wall
  99.             //outf << leftH << ' ' << rightH << endl;
  100.            
  101.             int leftN = st+j;
  102.             int rightN = st+j+1;
  103.             //outf << leftN << ' ' << rightN << endl;
  104.            
  105.             edges.push_back({vert,{rightN, leftN}});
  106.            
  107.             if (i != m+1) //if can connect up
  108.             {
  109.                 int leftUp = leftN+(n+1);
  110.                 int rightUp = rightN+(n+1);
  111.                 //outf << leftUp << ' ' << rightUp << endl;
  112.                
  113.                 if (j==1) edges.push_back({leftH,{leftN, leftUp}});
  114.                 edges.push_back({rightH, {rightN, rightUp}});
  115.                
  116.             }
  117.            
  118.         }
  119.         //outf << endl;
  120.     }
  121.    
  122.     stable_sort(edges.begin(), edges.end());
  123.    
  124.     for (int i = 1; i <= total; i++) par[i] = i;
  125.    
  126.     ll ret = 0;
  127.    
  128.     int connect = 0;
  129.    
  130.     for (int i = 0; i < edges.size(); i++)
  131.     {
  132.         if (connect == total-1) break;
  133.        
  134.         int len = edges[i].first;
  135.         int a = edges[i].second.first;
  136.         int b = edges[i].second.second;
  137.        
  138.         if (find(a) != find(b))
  139.         {
  140.             merge(a, b);
  141.             ret += len;
  142.             connect++;
  143.         }
  144.        
  145.     }
  146.    
  147.     outf << ret << '\n';
  148.    
  149.     return 0;
  150.    
  151. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement