oj.uz

Submission #785163

# Submission time Handle Problem Language Result Execution time Memory
785163 2023-07-17T06:32:11 Z 이동현(#10024) Raspad (COI17_raspad) C++17
0 / 100
 343 ms 27360 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #define int long long
using namespace std;

const int NS = (int)1e5 + 4;
int n, m;
int a[NS][54];

int i;
struct Dsu{
    int n, allcnt, rtcnt;
    vector<int> pr;
    vector<vector<int>> merge;
    Dsu(int m){
        n = m;
        pr.resize(n);
        iota(pr.begin(), pr.end(), 0);
        allcnt = rtcnt = 0;
    }

    int fd(int x){
        return (x == pr[x] ? x : pr[x] = fd(pr[x]));
    }

    void unite(int x, int y){
        x = fd(x), y = fd(y);
        if(x == y) return;
        if(x > y){
            swap(x, y);
        }

        pr[y] = x;
        --allcnt;
        if(x < m && y < m){
            --rtcnt;
            merge.push_back({i, x, y});
        }
    }
};

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

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

    int ans = 0;
    auto dnc = [&](auto&&self, int s, int e)->void{
        int mid = s + e >> 1;
        if(s < e){
            self(self, s, mid);
            self(self, mid + 1, e);
        }
        else{
            Dsu gr(m);
            for(int j = 0; j < m; ++j){
                if(a[s][j]){
                    ++gr.allcnt;
                    if(j && a[s][j - 1]){
                        gr.unite(j - 1, j);
                    }
                }
            }
            ans += gr.allcnt;
            // cout << s << ' ' << e << ' ' << ans << endl;
            return;
        }

        int urow = mid - s + 1;
        int drow = e - mid;
        Dsu up(urow * m);
        Dsu down(drow * m);
        
        // cout << s << ' ' << e << ' ' << ans << endl;

        vector<vector<int>> uop, dop;
        for(i = mid + 1; i <= e; ++i){
            for(int j = 0; j < m; ++j){
                if(!a[i][j]){
                    continue;
                }
                ++down.allcnt;
                if(j && a[i][j - 1]) down.unite((i - mid - 1) * m + j - 1, (i - mid - 1) * m + j);
                if(i > mid + 1){
                    if(a[i - 1][j]) down.unite((i - mid - 2) * m + j, (i - mid - 1) * m + j);
                }
                else{
                    ++down.rtcnt;
                }
            }

            // cout << s << ' ' << e << ' ' << i << ' ' << down.allcnt << ' ' << down.rtcnt << endl;

            ans += (down.allcnt - down.rtcnt) * (mid - s + 1);
        }

        for(i = mid; i >= s; --i){
            for(int j = 0; j < m; ++j){
                if(!a[i][j]){
                    continue;
                }
                ++up.allcnt;
                if(j && a[i][j - 1]) up.unite((mid - i) * m + j - 1, (mid - i) * m + j);
                if(i < mid){
                    if(a[i + 1][j]) up.unite((mid - i) * m + j, (mid - i - 1) * m + j);
                }
                else{
                    ++up.rtcnt;
                }
            }

            ans += (up.allcnt - up.rtcnt) * (e - mid);
        }

        Dsu test(m * 2);
        for(int i = 0; i < 2; ++i){
            for(int j = 0; j < m; ++j){
                if(!a[i + mid][j]) continue;
                ++test.allcnt;
                if(j && a[i + mid][j - 1]) test.unite(i * m + j, i * m + j - 1);
                if(i && a[i + mid - 1][j]) test.unite(i * m + j, i * m - m + j);
            }
        }

        Dsu gr(m);
        int i = 0, ilst = mid;
        while(i < (int)up.merge.size() && up.merge[i][0] == mid){
            gr.unite(up.merge[i][1], up.merge[i][2]);
            ++i;
        }
        while(true){
            int ilen = (i < (int)up.merge.size() ? up.merge[i][0] : s - 1);
            ilen = ilst - ilen;
            ilst = ilst - ilen;

            Dsu ngr = gr;
            int j = 0, jlst = mid + 1;
            while(j < (int)down.merge.size() && down.merge[j][0] == mid + 1){
                ngr.unite(down.merge[j][1], down.merge[j][2]);
                ++j;
            }
            ngr.allcnt = test.allcnt;

            while(true){
                int jlen = (j < (int)down.merge.size() ? down.merge[j][0] : e + 1);
                jlen = jlen - jlst;
                jlst = jlen + jlst;

                // cout << s << ' ' << e << ' ' << ilen << ' ' << jlen << ' ' << ngr.allcnt << endl;

                ans += ilen * jlen * ngr.allcnt;
                if(j == (int)down.merge.size()) break;
                ngr.unite(down.merge[j][1], down.merge[j][2]);
                ++j;
            }

            if(i == (int)up.merge.size()) break;
            gr.unite(up.merge[i][1], up.merge[i][2]);
            ++i;
        }

        // cout << s << ' ' << e << ' ' << ans << endl;
    };

    dnc(dnc, 0, n - 1);

    cout << ans << '\n';

    return 0;
}

Compilation message

raspad.cpp: In instantiation of 'main()::<lambda(auto:23&&, int, int)> [with auto:23 = main()::<lambda(auto:23&&, int, int)>&]':
raspad.cpp:175:22:   required from here
raspad.cpp:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         int mid = s + e >> 1;
      |                   ~~^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 13696 KB Output is correct
2 Incorrect 343 ms 27360 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -