Submission #547748

#	Time	Username	Problem	Language	Result	Execution time	Memory
547748		Lam_lai_cuoc_doi	Raspad (COI17_raspad)	C++17	100 / 100	3922 ms	94520 KiB

raspad

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 1e5 + 5;

struct dsu
{
    int par[N * 50];

    dsu()
    {
        memset(par, -1, sizeof par);
    }

    int findpar(int v)
    {
        return par[v] < 0 ? v : par[v] = findpar(par[v]);
    }

    bool Merge(int u, int v)
    {
        u = findpar(u);
        v = findpar(v);

        if (u == v)
            return false;

        if (par[u] < par[v])
            swap(u, v);

        par[v] += par[u];
        par[u] = v;

        return true;
    }
} f, g;
int m, n;
ll ans(0);

string s[N];

void Read()
{
    cin >> m >> n;

    for (int i = 1; i <= m; ++i)
    {
        cin >> s[i];
        s[i] = " " + s[i];
    }
}

#define pos(x, y) ((x - 1) * n + y)

int mask[N][51];
int cnt[N];
ll sum[N];
int order[N * 50];
vector<int> pos;

int Get(int mask1[51], int mask2[51])
{
    int res(0);

    for (int i = 1; i <= n; ++i)
        if (mask1[i] != 0 && mask2[i] != 0 && g.Merge(mask1[i], mask2[i] + 50))
            ++res;

    for (int i = 1; i <= n; ++i)
    {
        if (mask1[i] != 0)
            g.par[mask1[i]] = -1;
        if (mask2[i] != 0)
            g.par[mask2[i] + 50] = -1;
    }

    return res;
}

void DAC(int l, int r)
{
    if (l == r)
    {
        for (int i = 1, j = 1; i <= n; ++i)
        {
            while (j <= n && s[l][i] == s[l][j])
                ++j;

            ans += s[l][i] == '1';

            i = j - 1;
        }
        return;
    }

    int mid = (l + r) / 2;
    pos.clear();

    {
        int tmpcnt = 0, numcom = 0;
        ll tmpsum = 0;

        for (int i = mid + 1; i <= r; ++i)
        {
            for (int j = 1; j <= n; ++j)
                if (s[i][j] == '1')
                {
                    ++numcom;

                    if (i != mid + 1 && s[i - 1][j] == '1' && f.Merge(pos(i - 1, j), pos(i, j)))
                        --numcom;
                    if (s[i][j - 1] == '1' && f.Merge(pos(i, j - 1), pos(i, j)))
                        --numcom;
                }

            for (int j = 1, p = 0; j <= n; ++j)
            {
                int root = f.findpar(pos(mid + 1, j));
                if (s[mid + 1][j] == '1' && !order[root])
                    order[root] = ++p;

                mask[i][j] = order[root];
            }

            for (int j = 1; j <= n; ++j)
                order[f.findpar(pos(mid + 1, j))] = 0;

            if (i != mid + 1)
                for (int j = 1; j <= n; ++j)
                    if (mask[i][j] != mask[i - 1][j])
                    {
                        tmpcnt = tmpsum = 0;
                        pos.emplace_back(i);
                        break;
                    }

            ++tmpcnt;
            tmpsum += numcom;

            cnt[i] = tmpcnt;
            sum[i] = tmpsum;
        }

        pos.emplace_back(r + 1);
    }

    {
        int numcom(0);

        for (int i = mid; i >= l; --i)
        {
            for (int j = 1; j <= n; ++j)
                if (s[i][j] == '1')
                {
                    ++numcom;

                    if (i != mid && s[i + 1][j] == '1' && f.Merge(pos(i + 1, j), pos(i, j)))
                        --numcom;
                    if (s[i][j - 1] == '1' && f.Merge(pos(i, j - 1), pos(i, j)))
                        --numcom;
                }

            for (int j = 1, p = 0; j <= n; ++j)
            {
                int root = f.findpar(pos(mid, j));
                if (s[mid][j] == '1' && !order[root])
                    order[root] = ++p;

                mask[i][j] = order[root];
            }

            for (int j = 1; j <= n; ++j)
                order[f.findpar(pos(mid, j))] = 0;

            for (auto j : pos)
                ans += sum[j - 1] + 1ll * cnt[j - 1] * (numcom - Get(mask[i], mask[j - 1]));
        }
    }

    for (int i = l; i <= r; ++i)
        for (int j = 1; j <= n; ++j)
            if (s[i][j] == '1')
                f.par[pos(i, j)] = -1;

    DAC(l, mid);
    DAC(mid + 1, r);
}

void Solve()
{
    DAC(1, m);

    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("tests.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case #" << _ << ": ";
        Read();
        Solve();
    }
    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

/*
 */

Compilation message (stderr)

raspad.cpp: In function 'void read(T&)':
raspad.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^
raspad.cpp: In function 'int32_t main()':
raspad.cpp:219:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
raspad.cpp:220:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39