fork download 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. using pii = pair<int, int>;
  8. const int N = 5e2 + 5;
  9. const int A = 250000 + 5;
  10. int Dx[] = {-1, 1, 0, 0};
  11. int Dy[] = {0, 0, -1, 1};
  12.  
  13. int n, m, T, ans = 0;
  14. int a[N][N], par[A], sz[A], Group[A];
  15. struct Edge {
  16.     int u, v, w;
  17. };
  18. vector<Edge> E;
  19.  
  20. inline int getID(int x, int y) {
  21.     return (x - 1) * m + y;
  22. }
  23. inline pii getXY(int id) {
  24.     return (pii) {(id - 1) / m + 1, (id % m) ? id % m : m};
  25. }
  26.  
  27. int findPar(int u) {
  28.     if (par[u] == u) return u;
  29.     return par[u] = findPar(par[u]);
  30. }
  31. bool joint(int u, int v) {
  32.     u = findPar(u), v = findPar(v);
  33.     if (u == v) return 0;
  34.     if (sz[u] < sz[v]) swap(u, v);
  35.     par[v] = u;
  36.     sz[u] += sz[v];
  37.     Group[u] += Group[v];
  38.  
  39.     Group[v] = sz[v] = 0;
  40.     return 1;
  41. }
  42.  
  43. signed main() {
  44.     cin.tie(NULL)->sync_with_stdio(false);
  45.     if(ifstream("SKILEVEL.inp")) {
  46.         freopen("SKILEVEL.inp", "r", stdin);
  47.         freopen("SKILEVEL.out", "w", stdout);
  48.     }
  49.     cin >> n >> m >> T;
  50.     for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
  51.     for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
  52.         int ok; cin >> ok;
  53.         int id = getID(i, j);
  54.         if (ok) Group[id] = 1;
  55.         par[id] = id;
  56.         sz[id] = 1;
  57.     }
  58.     if (T <= 1) return cout << 0, 0;
  59.     for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
  60.         int u = getID(i, j);
  61.         for (int mov = 0; mov < 4; mov++) {
  62.             int tx = i + Dx[mov], ty = j + Dy[mov];
  63.             if (!tx || !ty || tx > n || ty > m) continue;
  64.             int v = getID(tx, ty);
  65.             // cerr << u << " " << v << " " << abs(a[i][j] - a[tx][ty]) << "\n";
  66.             E.push_back({u, v, abs(a[i][j] - a[tx][ty])});
  67.         }
  68.     }
  69.     sort(E.begin(), E.end(), [&](Edge &a, Edge &b) {return a.w < b.w;});
  70.     for (Edge &e: E) {
  71.         // cerr << "HIC";
  72.         if (joint(e.u, e.v)) {
  73.             // cerr << "?";
  74.             int u = findPar(e.u);
  75.             if (sz[u] >= T) {
  76.                 ans += Group[u] * e.w;
  77.                 Group[u] = 0;
  78.             }
  79.         }
  80.     }
  81.     cout << ans;
  82.     return 0;
  83. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/PO6Fld
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

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!