fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 25e3 + 5; 
  12.  
  13. int P, Q, n, m;  
  14. int a[N], b[N];
  15.  
  16. int what_subtask() {
  17. 	if (max(n, m) <= 25e2) return 1; 
  18. 	return 2; 
  19. }
  20.  
  21. namespace sub1 {
  22. 	const int N = 25e2 + 5; 
  23.  
  24. 	int getIndex(int i, int j) {
  25. 		return (j - 1) * n + i;   
  26. 	}
  27.  
  28. 	struct Edge {
  29. 		int u, v, w; 
  30. 		bool operator<(const Edge& other) const {
  31. 			return w < other.w; 
  32. 		}
  33. 	}; 
  34.  
  35. 	vector<Edge> edges;  
  36.  
  37. 	int p[N * N], sz[N * N]; 
  38.  
  39. 	void initSet() {
  40. 		for (int u = 1; u <= n * m; u++) {
  41. 			p[u] = u;  
  42. 			sz[u] = 1;  
  43. 		}
  44. 	}
  45.  
  46. 	int findSet(int u) {
  47. 		if (p[u] == u) return u; 
  48. 		return p[u] = findSet(p[u]); 
  49. 	}
  50.  
  51. 	bool unionSet(int u, int v) {
  52. 		u = findSet(u); 
  53. 		v = findSet(v); 
  54. 		if (u == v) return false;  
  55. 		if (sz[u] < sz[v]) swap(u, v);  
  56. 		p[v] = u;  
  57. 		sz[u] += sz[v];
  58. 		return true; 
  59. 	}
  60.  
  61. 	void solve() {
  62. 		// Coi mỗi căn phòng là một đỉnh
  63. 		// Trọng số của cạnh nối giữa 2 đỉnh chính bằng chiều dài bức tường ngăn giữa 2 căn phòng tương ứng với 2 đỉnh đó
  64. 		for (int i = 1; i <= n; i++) {
  65. 			for (int j = 1; j <= m; j++) {
  66. 				int u = getIndex(i, j);  
  67. 				if (j + 1 <= m) { // căn phòng bên trên
  68. 					int v = getIndex(i, j + 1), w = a[i] - a[i - 1]; 
  69. 					edges.push_back({u, v, w});  
  70. 				}
  71. 				if (i + 1 <= n) { // căn phòng bên phải
  72. 					int v = getIndex(i + 1, j), w = b[j] - b[j - 1]; 
  73. 					edges.push_back({u, v, w}); 
  74. 				}
  75. 			}
  76. 		}
  77.  
  78. 		sort(edges.begin(), edges.end());   
  79.  
  80. 		initSet();   
  81.  
  82. 		ll ans = 0;  
  83. 		for (Edge e : edges) {
  84. 			if (unionSet(e.u, e.v)) ans += e.w; 
  85. 		}
  86.  
  87. 		cout << ans << '\n'; 
  88. 	}
  89. }
  90.  
  91. namespace sub2 {
  92. 	// Các cạnh ở chung một hàng hay chung một cột thì sẽ có trọng số như nhau
  93. 	const int N = 25e3 + 5;   
  94.  
  95. 	struct Data {
  96. 		int w; 
  97. 		int type; // 0 = cột, 1 = hàng
  98. 		bool operator<(const Data& other) const {
  99. 			return w < other.w; 
  100. 		}
  101. 	}; 
  102.  
  103. 	vector<Data> data_list;  
  104.  
  105. 	void solve() {
  106. 		for (int i = 1; i <= n; i++) {
  107. 			int w = a[i] - a[i - 1]; 
  108. 			data_list.push_back({w, 0}); 
  109. 		}
  110.  
  111. 		for (int j = 1; j <= m; j++) {
  112. 			int w = b[j] - b[j - 1]; 
  113. 			data_list.push_back({w, 1}); 
  114. 		}
  115.  
  116. 		sort(data_list.begin(), data_list.end());  
  117.  
  118. 		ll ans = 0; 
  119. 		int cnt_col = 0, cnt_row = 0;  
  120. 		for (Data cur : data_list) {
  121. 			if (cur.type == 0) {
  122. 				if (cnt_col > 0 && cnt_row > 0) {
  123. 					ans += 1ll * cur.w * (m - cnt_row);  
  124. 				}
  125. 				else {
  126. 					ans += 1ll * cur.w * (m - 1); 
  127. 				}
  128. 				cnt_col++; 
  129. 			}
  130. 			else {
  131. 				if (cnt_row > 0 && cnt_col > 0) {
  132. 					ans += 1ll * cur.w * (n - cnt_col);  
  133. 				}
  134. 				else {
  135. 					ans += 1ll * cur.w * (n - 1); 
  136. 				}
  137. 				cnt_row++; 
  138. 			}
  139. 		}
  140.  
  141. 		cout << ans << '\n'; 
  142. 	}
  143. }
  144.  
  145. int main() {
  146. 	ios::sync_with_stdio(false); 
  147. 	cin.tie(nullptr); 	
  148. 	cin >> P >> Q >> n >> m; 
  149.  
  150. 	a[0] = 0; 
  151. 	for (int i = 1; i <= n; i++) cin >> a[i];
  152. 	a[++n] = P;   
  153. 	sort(a, a + n + 1);  
  154.  
  155. 	b[0] = 0;  
  156. 	for (int i = 1; i <= m; i++) cin >> b[i]; 
  157. 	b[++m] = Q;  
  158. 	sort(b, b + m + 1); 
  159.  
  160. 	int subtask = what_subtask();  
  161.  
  162. 	if (subtask == 1) sub1::solve();  
  163. 	if (subtask == 2) sub2::solve(); 
  164. }
Success #stdin #stdout 0.01s 5584KB
comments (?)
stdin
copy 
15 16 5 2
3
5
11
6
7
9
3
stdout
copy 
45
https://ideone.com/7sZGz5
language:
C++14 (gcc 8.3)
created:
298 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!