Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ID: bradyawn
- PROG: contest
- LANG: C++11
- */
- #include <iostream>
- #include <algorithm>
- #include <iomanip>
- #include <fstream>
- #include <vector>
- #include <deque>
- #include <string>
- #include <cmath>
- #include <map>
- #include <utility>
- #include <algorithm>
- #include <set>
- #include <ctime>
- #include <queue>
- #include <stack>
- #include <bitset>
- #include <random>
- #include <cstring>
- using namespace std;
- typedef long long ll;
- typedef pair<int,int> i2;
- typedef pair<ll,ll> ll2;
- int par[2001*2001+1];
- int r[2001*2001+1];
- int find(int x)
- {
- if (par[x] == x) return x;
- return par[x] = find(par[x]);
- }
- void merge(int x, int y) //merge set x under y
- {
- int setX = find(x);
- int setY = find(y);
- if (r[setX] == r[setY])
- {
- par[setX] = setY;
- r[setY]++;
- }
- else if (r[setX] < r[setY]) par[setX] = setY;
- else par[setY] = setX;
- }
- int a, b, n, m;
- int main()
- {
- ifstream inf("fencedin.in");
- ofstream outf("fencedin.out");
- //outf << setprecision(10);
- //ios_base::sync_with_stdio(0);
- //inf.tie(0);
- inf >> a >> b >> n >> m;
- vector<int> v(n);
- vector<int> h(m);
- for (int i = 0; i < n; i++) inf >> v[i];
- for (int i = 0; i < m; i++) inf >> h[i];
- //Makes easier to parse
- h.push_back(0);
- h.push_back(b);
- v.push_back(0);
- v.push_back(a);
- stable_sort(v.begin(), v.end());
- stable_sort(h.begin(), h.end());
- //for (int i = 0; i < n; i++) outf << v[i] << " \n"[i==n-1];
- //for (int i = 0; i < m; i++) outf << h[i] << " \n"[i==m-1];
- int total = (n+1)*(m+1);
- vector<pair<int, i2>> edges; //{len,{st,ed}}
- for (int i = 1; i <= m+1; i++) //below horizontal lines
- {
- int st = (i-1)*(n+1);
- int vert = h[i]-h[i-1];
- for (int j = 1; j <= n; j++) //vertical
- {
- int leftH = v[j]-v[j-1]; //horizontal wall
- int rightH = v[j+1]-v[j]; //horizontal wall
- //outf << leftH << ' ' << rightH << endl;
- int leftN = st+j;
- int rightN = st+j+1;
- //outf << leftN << ' ' << rightN << endl;
- edges.push_back({vert,{rightN, leftN}});
- if (i != m+1) //if can connect up
- {
- int leftUp = leftN+(n+1);
- int rightUp = rightN+(n+1);
- //outf << leftUp << ' ' << rightUp << endl;
- if (j==1) edges.push_back({leftH,{leftN, leftUp}});
- edges.push_back({rightH, {rightN, rightUp}});
- }
- }
- //outf << endl;
- }
- stable_sort(edges.begin(), edges.end());
- for (int i = 1; i <= total; i++) par[i] = i;
- ll ret = 0;
- int connect = 0;
- for (int i = 0; i < edges.size(); i++)
- {
- if (connect == total-1) break;
- int len = edges[i].first;
- int a = edges[i].second.first;
- int b = edges[i].second.second;
- if (find(a) != find(b))
- {
- merge(a, b);
- ret += len;
- connect++;
- }
- }
- outf << ret << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement