Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2019
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.98 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define s second
  6. #define f first
  7. #define ll long long
  8. #define pb push_back
  9.  
  10. const int N = 502;
  11.  
  12. struct kek{
  13. int w, x, y, xx, yy;
  14. }rib[N * N * 2];
  15.  
  16. bool operator <(const kek &a, const kek &b){
  17. return a.w < b.w;
  18. }
  19.  
  20. int n, m, g, tol, a[N][N], used[N][N], st, t, tt;
  21.  
  22. ll ans;
  23.  
  24. int p[N + N * N];
  25.  
  26. vector <pair <int, int> > root[N * N + N];
  27.  
  28. int fin(int v){
  29. if (p[v] == v)
  30. return v;
  31. return p[v] = fin(p[v]);
  32. }
  33.  
  34. void un(int v, int vv, int lol){
  35. pair <int, int> from;
  36. if (root[v].size() < root[vv].size()){
  37. swap(v, vv);
  38. }
  39. int mem = root[v].size();
  40.  
  41. p[vv] = v;
  42. for (int i = 0; i < root[vv].size(); i++){
  43. root[v].pb(root[vv][i]);
  44. }
  45.  
  46. if (mem >= tol && root[vv].size() >= tol){
  47. root[vv].clear();
  48. return;
  49. }
  50.  
  51. if (mem >= tol && root[vv].size() < tol){
  52. for (int i = 0; i < root[vv].size(); i++){
  53. from = root[vv][i];
  54. if (used[from.f][from.s]){
  55. ans += (ll)lol;
  56. }
  57. }
  58. root[vv].clear();
  59. return;
  60. }
  61.  
  62. if (root[v].size() >= tol){
  63. for (int i = 0; i < root[v].size(); i++){
  64. from = root[v][i];
  65. if (used[from.f][from.s]){
  66. ans += (ll)lol;
  67. }
  68. }
  69. }
  70. root[vv].clear();
  71. return;
  72. }
  73.  
  74.  
  75.  
  76. int main(){
  77. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  78. cin >> n >> m >> tol;
  79. for (int i = 1; i <= n; i++){
  80. for (int j = 1; j <= m; j++){
  81. cin >> a[i][j];
  82. }
  83. }
  84. for (int i = 1; i <= n; i++){
  85. for (int j = 1; j <= m; j++){
  86. cin >> used[i][j];
  87. }
  88. }
  89.  
  90. for (int i = 1; i <= n; i++){
  91. for (int j = 1; j <= m; j++){
  92. p[i * 500 + j] = i * 500 + j;
  93. root[i * 500 + j].pb({i, j});
  94. }
  95. }
  96.  
  97. for (int i = 1; i <= n; i++){
  98. for (int j = 1; j <= m; j++){
  99. if (i < n){
  100. g++;
  101. rib[g].w = abs(a[i][j] - a[i + 1][j]);
  102. rib[g].x = i;
  103. rib[g].y = j;
  104. rib[g].xx = i + 1;
  105. rib[g].yy = j;
  106. }
  107. if (j < m){
  108. g++;
  109. rib[g].w = abs(a[i][j] - a[i][j + 1]);
  110. rib[g].x = i;
  111. rib[g].y = j;
  112. rib[g].xx = i;
  113. rib[g].yy = j + 1;
  114. }
  115. }
  116. }
  117.  
  118. sort (rib + 1, rib + g + 1);
  119.  
  120. //cout << g << endl;
  121.  
  122. for (int i = 1; i <= g; i = i){
  123. st = rib[i].w;
  124. while (rib[i].w == st && i <= g){
  125. t = fin(rib[i].x * 500 + rib[i].y);
  126. tt = fin(rib[i].xx * 500 + rib[i].yy);
  127. //cout << t << " " << tt << " " << st << endl;
  128. if (t != tt){
  129. un(t, tt, st);
  130. }
  131. //cout << ans << endl;
  132. i++;
  133. }
  134. }
  135. cout << ans;
  136. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement