Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define s second
- #define f first
- #define ll long long
- #define pb push_back
- const int N = 502;
- struct kek{
- int w, x, y, xx, yy;
- }rib[N * N * 2];
- bool operator <(const kek &a, const kek &b){
- return a.w < b.w;
- }
- int n, m, g, tol, a[N][N], used[N][N], st, t, tt;
- ll ans;
- int p[N + N * N];
- vector <pair <int, int> > root[N * N + N];
- int fin(int v){
- if (p[v] == v)
- return v;
- return p[v] = fin(p[v]);
- }
- void un(int v, int vv, int lol){
- pair <int, int> from;
- if (root[v].size() < root[vv].size()){
- swap(v, vv);
- }
- int mem = root[v].size();
- p[vv] = v;
- for (int i = 0; i < root[vv].size(); i++){
- root[v].pb(root[vv][i]);
- }
- if (mem >= tol && root[vv].size() >= tol){
- root[vv].clear();
- return;
- }
- if (mem >= tol && root[vv].size() < tol){
- for (int i = 0; i < root[vv].size(); i++){
- from = root[vv][i];
- if (used[from.f][from.s]){
- ans += (ll)lol;
- }
- }
- root[vv].clear();
- return;
- }
- if (root[v].size() >= tol){
- for (int i = 0; i < root[v].size(); i++){
- from = root[v][i];
- if (used[from.f][from.s]){
- ans += (ll)lol;
- }
- }
- }
- root[vv].clear();
- return;
- }
- int main(){
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- cin >> n >> m >> tol;
- for (int i = 1; i <= n; i++){
- for (int j = 1; j <= m; j++){
- cin >> a[i][j];
- }
- }
- for (int i = 1; i <= n; i++){
- for (int j = 1; j <= m; j++){
- cin >> used[i][j];
- }
- }
- for (int i = 1; i <= n; i++){
- for (int j = 1; j <= m; j++){
- p[i * 500 + j] = i * 500 + j;
- root[i * 500 + j].pb({i, j});
- }
- }
- for (int i = 1; i <= n; i++){
- for (int j = 1; j <= m; j++){
- if (i < n){
- g++;
- rib[g].w = abs(a[i][j] - a[i + 1][j]);
- rib[g].x = i;
- rib[g].y = j;
- rib[g].xx = i + 1;
- rib[g].yy = j;
- }
- if (j < m){
- g++;
- rib[g].w = abs(a[i][j] - a[i][j + 1]);
- rib[g].x = i;
- rib[g].y = j;
- rib[g].xx = i;
- rib[g].yy = j + 1;
- }
- }
- }
- sort (rib + 1, rib + g + 1);
- //cout << g << endl;
- for (int i = 1; i <= g; i = i){
- st = rib[i].w;
- while (rib[i].w == st && i <= g){
- t = fin(rib[i].x * 500 + rib[i].y);
- tt = fin(rib[i].xx * 500 + rib[i].yy);
- //cout << t << " " << tt << " " << st << endl;
- if (t != tt){
- un(t, tt, st);
- }
- //cout << ans << endl;
- i++;
- }
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement