Submission #1345873

#TimeUsernameProblemLanguageResultExecution timeMemory
1345873gkos5678Raspad (COI17_raspad)C++20
26 / 100
6095 ms6436 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 1e5 + 7;
const int maxm = 55;

int n, m, bc, p[maxn * maxm], s[maxm * maxn];
ll ans;
bool b[maxm][maxn];

int get(int x){
    if (x == p[x]) return x;
    return get(p[x]);
}

void unite(int a, int b){
    a = get(a), b = get(b);
    if (a == b) return;
    bc--;
    if (s[a] > s[b]) swap(a, b);
    p[a] = b;
    s[b] += s[a];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            char c;
            cin >> c;
            b[j][i] = (c == '1');
        }
    }

    for (int i = 1; i <= n; i++){
        bc = 0;
        for (int j = i; j <= n; j++){
            for (int k = 1; k <= m; k++){
                if (b[k][j]){
                    p[j * m + k] = j * m + k;
                    s[j * m + k] = 1;
                }
            }
        }
        for (int j = i; j <= n; j++){
            for (int k = 1; k <= m; k++)
                bc += b[k][j];
            for (int k = 1; k < m; k++)
                if (b[k][j] && b[k + 1][j])
                    unite(j * m + k, j * m + k + 1);
            ans += (ll)bc;
            for (int k = 1; k <= m; k++)
                if (b[k][j] && b[k][j + 1])
                    unite(j * m + k, (j + 1) * m + k);
        }
    }
    cout << ans << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...