oj.uz

답안 #250838

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250838 2020-07-19T09:24:09 Z VEGAnn Raspad (COI17_raspad) C++14
26 / 100
 624 ms 23264 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100100;
const int M = 53;
ll ans = 0;
bool tp[N][M];
int n, m, pre[N * M], lft[M][M], rgt[M][M], clf[M], crt[M];
int lst[N * M], ind[N * M], tt, pred[2 * M];
ll ans_lf[M], ans_rt[M];

int get(int x) { return (pre[x] == x ? pre[x] : pre[x] = get(pre[x])); }
int get_o(int x) { return (pred[x] == x ? pred[x] : pred[x] = get_o(pred[x])); }

void calc(int lf, int rt){
    if (lf == rt){
        ans += tp[lf][0];

        for (int j = 1; j < m; j++){
            if (!tp[lf][j]) continue;

            if (!tp[lf][j - 1])
                ans++;
        }
        return;
    }

    int ko_lf = 1, ko_rt = 1;

    int md = (lf + rt) >> 1;

    // left side

    int siz = 0;

    for (int j = 0; j < m; j++){
        int loc = md * m + j;

        pre[loc] = loc;

        if (!tp[md][j]) continue;

        siz++;

        if (j > 0 && tp[md][j - 1]) {
            pre[get(loc)] = get(pre[loc - 1]);
            siz--;
        }
    }

    ans_lf[0] = siz;
    clf[0] = 1;

    for (int j = 0; j < m; j++)
        lft[0][j] = get(pre[md * m + j]);

    for (int row = md - 1; row >= lf; row--){
        for (int j = 0; j < m; j++){
            if (!tp[row][j]) continue;

            siz++;

            int loc = row * m + j;

            pre[loc] = loc;

            if (j > 0 && tp[row][j - 1] && get(loc) != get(loc - 1)) {
                pre[get(loc)] = get(pre[loc - 1]);
                siz--;
            }

            if (tp[row + 1][j] && get(loc) != get(loc + m)){
                siz--;
                pre[get(loc)] = get(loc + m);
            }
        }

        bool was = 0;

        for (int j = 0; j < m; j++) {
            lft[ko_lf][j] = get(pre[md * m + j]);

            if (tp[md][j] && lft[ko_lf][j] != lft[ko_lf - 1][j])
                was = 1;
        }

        if (was){
            clf[ko_lf] = 1;
            ans_lf[ko_lf] = siz;
            ko_lf++;
        } else {
            clf[ko_lf - 1]++;
            ans_lf[ko_lf - 1] += siz;
        }
    }

    // right side

    siz = 0;

    for (int j = 0; j < m; j++){
        int loc = md * m + m + j;

        pre[loc] = loc;

        if (!tp[md + 1][j]) continue;

        siz++;

        if (j > 0 && tp[md + 1][j - 1]) {
            pre[get(loc)] = get(pre[loc - 1]);
            siz--;
        }
    }

    ans_rt[0] = siz;

    crt[0] = 1;

    for (int j = 0; j < m; j++)
        rgt[0][j] = get(pre[md * m + m + j]);

    for (int row = md + 2; row <= rt; row++){
        for (int j = 0; j < m; j++){
            if (!tp[row][j]) continue;

            siz++;

            int loc = row * m + j;

            pre[loc] = loc;

            if (j > 0 && tp[row][j - 1] && get(loc) != get(loc - 1)) {
                pre[get(loc)] = get(pre[loc - 1]);
                siz--;
            }

            if (tp[row - 1][j] && get(loc) != get(loc - m)){
                siz--;
                pre[get(loc)] = get(loc - m);
            }
        }

        bool was = 0;

        for (int j = 0; j < m; j++) {
            rgt[ko_rt][j] = get(pre[md * m + m + j]);

            if (tp[md + 1][j] && rgt[ko_rt][j] != rgt[ko_rt - 1][j])
                was = 1;
        }

        if (was){
            crt[ko_rt] = 1;
            ans_rt[ko_rt] = siz;
            ko_rt++;
        } else {
            crt[ko_rt - 1]++;
            ans_rt[ko_rt - 1] += siz;
        }
    }

    for (int le = 0; le < ko_lf; le++)
    for (int ri = 0; ri < ko_rt; ri++){
        ll nw = 0, dlt = ll(crt[ri]) * ll(clf[le]);

        ans += ans_lf[le] * ll(crt[ri]) + ans_rt[ri] * ll(clf[le]);

        tt++;

        int indx = 0;

        for (int j = 0; j < m; j++){
            pred[j] = j;
            pred[j + m] = j + m;

            if (lst[rgt[ri][j]] != tt){
                lst[rgt[ri][j]] = tt;
                ind[rgt[ri][j]] = j;
            }

            pred[j] = ind[rgt[ri][j]];


            if (lst[lft[le][j]] != tt){
                lst[lft[le][j]] = tt;
                ind[lft[le][j]] = j + m;
            }

            pred[j + m] = ind[lft[le][j]];
        }

        for (int j = 0; j < m; j++){
            if (!tp[md][j] || !tp[md + 1][j]) continue;

            int fi = get_o(pred[j]);
            int se = get_o(pred[j + m]);

            if (fi == se) continue;

            nw++;

            pred[fi] = se;
        }

        ans -= dlt * nw;
    }

    calc(lf, md);
    calc(md + 1, rt);
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

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

    calc(0, n - 1);

    cout << ans;

    return 0;
}

Compilation message

raspad.cpp: In function 'void calc(int, int)':
raspad.cpp:171:13: warning: unused variable 'indx' [-Wunused-variable]
         int indx = 0;
             ^~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 7 ms 1024 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 18 ms 1024 KB Output is correct
10 Correct 5 ms 896 KB Output is correct
11 Correct 10 ms 1024 KB Output is correct
12 Correct 7 ms 896 KB Output is correct
13 Correct 10 ms 1024 KB Output is correct

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 11128 KB Output is correct
2 Correct 392 ms 23144 KB Output is correct
3 Incorrect 624 ms 23264 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 7 ms 1024 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 18 ms 1024 KB Output is correct
10 Correct 5 ms 896 KB Output is correct
11 Correct 10 ms 1024 KB Output is correct
12 Correct 7 ms 896 KB Output is correct
13 Correct 10 ms 1024 KB Output is correct
14 Correct 164 ms 11128 KB Output is correct
15 Correct 392 ms 23144 KB Output is correct
16 Incorrect 624 ms 23264 KB Output isn't correct
17 Halted 0 ms 0 KB -