oj.uz

답안 #250830

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250830 2020-07-19T09:16:42 Z VEGAnn Raspad (COI17_raspad) C++14
61 / 100
 986 ms 94328 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100100;
const int M = 510;
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_lf < M && 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 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 7 ms 1408 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 20 ms 1664 KB Output is correct
10 Correct 4 ms 1280 KB Output is correct
11 Correct 10 ms 1536 KB Output is correct
12 Correct 7 ms 1280 KB Output is correct
13 Correct 10 ms 1408 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 33528 KB Output is correct
2 Correct 412 ms 68088 KB Output is correct
3 Correct 637 ms 68304 KB Output is correct
4 Correct 179 ms 61180 KB Output is correct
5 Correct 104 ms 20600 KB Output is correct
6 Correct 430 ms 67980 KB Output is correct
7 Correct 369 ms 67960 KB Output is correct
8 Correct 334 ms 54520 KB Output is correct

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 7 ms 1408 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 20 ms 1664 KB Output is correct
10 Correct 4 ms 1280 KB Output is correct
11 Correct 10 ms 1536 KB Output is correct
12 Correct 7 ms 1280 KB Output is correct
13 Correct 10 ms 1408 KB Output is correct
14 Correct 179 ms 33528 KB Output is correct
15 Correct 412 ms 68088 KB Output is correct
16 Correct 637 ms 68304 KB Output is correct
17 Correct 179 ms 61180 KB Output is correct
18 Correct 104 ms 20600 KB Output is correct
19 Correct 430 ms 67980 KB Output is correct
20 Correct 369 ms 67960 KB Output is correct
21 Correct 334 ms 54520 KB Output is correct
22 Correct 986 ms 77956 KB Output is correct
23 Runtime error 248 ms 94328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -