제출 #1357080

#제출 시각아이디문제언어결과실행 시간메모리
1357080gkos5678Raspad (COI17_raspad)C++20
100 / 100
954 ms5376 KiB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ppb pop_back

typedef long long ll;
typedef vector<int> vi;
struct tro{
    vi p;
    ll x, y;
};
typedef vector<tro> vtro;

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

int n, m, mn[2 * maxm], c[maxm];
bool b[maxm][maxn], vis[2 * maxm];
vi p, r, ls[2 * maxm], st;
vtro pr, acc;

void comb(tro &trt, vi &p){
    int c1 = 0, c2 = 0;
    for (int i = 1; i <= m; i++){
        c1 = max(c1, p[i]);
        c2 = max(c2, trt.p[i]);
    }
    for (int i = 1; i <= c1 + c2; i++){
        ls[i].clear();
        mn[i] = maxn;
        vis[i] = 0;
    }
    for (int i = 1; i <= m; i++){
        if (p[i] > 0 && trt.p[i] > 0){
            ls[p[i]].pb(trt.p[i] + c1);
            ls[trt.p[i] + c1].pb(p[i]);
        }
    }
    ll nd = 0, trc = 1;
    for (int i = 1; i <= c1 + c2; i++){
        if (vis[i]) continue;
        if (i > c1) nd++;
        st.pb(i);
        vis[i] = 1;
        while(!st.empty()){
            int tr = st.back();
            st.ppb();
            mn[tr] = trc;
            for (int ss : ls[tr]){
                if (!vis[ss]){
                    vis[ss] = 1;
                    st.pb(ss);
                }
            }
        }
        trc++;
    }
    for (int i = 1; i <= m; i++)
        p[i] = mn[p[i]];
    trt.p = p;
    trt.y += nd * trt.x;
}

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');
        }
    }

    ll ans = 0;
    for (int i = n; i > 0; i--){
        int trr = 1;
        p.clear();
        p.pb(0);
        for (int j = 1; j <= m; j++){
            if (b[j][i])
                p.pb(trr);
            else {
                p.pb(0);
                if (b[j - 1][i]) trr++;
            }
        }
        r = p;
        acc.clear();
        acc.pb({p, 1, 0});
        for (tro &trt : pr){
            for (int i = 1; i <= m; i++)
                r[i] = p[i];
            comb(trt, r);
            if (trt.p != acc.back().p){
                acc.pb(trt);
                continue;
            }
            acc.back().x += trt.x;
            acc.back().y += trt.y;
        }
        pr = acc;
        for (tro &trt : pr){
            ll bc = 0;
            for (int j = 1; j <= m; j++) c[j] = 0;
            for (int j = 1; j <= m; j++) c[trt.p[j]]++;
            for (int j = 1; j <= m; j++) bc += (c[j] > 0);
            ans += trt.x * bc + trt.y;
        }
    }

    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...