oj.uz

답안 #250835

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250835 2020-07-19T09:20:50 Z VEGAnn Raspad (COI17_raspad) C++14
26 / 100
 630 ms 23160 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 (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 (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;
        }
    }

    assert(ko_rt < M);

    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:173: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 6 ms 896 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 20 ms 1024 KB Output is correct
10 Correct 4 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 168 ms 11132 KB Output is correct
2 Correct 365 ms 23160 KB Output is correct
3 Incorrect 630 ms 23160 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 6 ms 896 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 20 ms 1024 KB Output is correct
10 Correct 4 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 168 ms 11132 KB Output is correct
15 Correct 365 ms 23160 KB Output is correct
16 Incorrect 630 ms 23160 KB Output isn't correct
17 Halted 0 ms 0 KB -