oj.uz

Submission #547745

# Submission time Handle Problem Language Result Execution time Memory
547745 2022-04-11T15:00:17 Z Lam_lai_cuoc_doi Raspad (COI17_raspad) C++17
26 / 100
 314 ms 40980 KB 
#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 * 10];

    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 * 10];
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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 9 ms 11348 KB Output is correct
3 Correct 7 ms 11296 KB Output is correct
4 Correct 7 ms 11364 KB Output is correct
5 Correct 6 ms 11288 KB Output is correct
6 Correct 6 ms 11348 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 9 ms 11348 KB Output is correct
3 Correct 7 ms 11296 KB Output is correct
4 Correct 7 ms 11364 KB Output is correct
5 Correct 6 ms 11288 KB Output is correct
6 Correct 6 ms 11348 KB Output is correct
7 Correct 16 ms 11732 KB Output is correct
8 Correct 5 ms 11348 KB Output is correct
9 Correct 29 ms 11724 KB Output is correct
10 Correct 12 ms 11684 KB Output is correct
11 Correct 23 ms 11728 KB Output is correct
12 Correct 16 ms 11644 KB Output is correct
13 Correct 21 ms 11768 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 25248 KB Output is correct
2 Runtime error 44 ms 40980 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 9 ms 11348 KB Output is correct
3 Correct 7 ms 11296 KB Output is correct
4 Correct 7 ms 11364 KB Output is correct
5 Correct 6 ms 11288 KB Output is correct
6 Correct 6 ms 11348 KB Output is correct
7 Correct 16 ms 11732 KB Output is correct
8 Correct 5 ms 11348 KB Output is correct
9 Correct 29 ms 11724 KB Output is correct
10 Correct 12 ms 11684 KB Output is correct
11 Correct 23 ms 11728 KB Output is correct
12 Correct 16 ms 11644 KB Output is correct
13 Correct 21 ms 11768 KB Output is correct
14 Correct 314 ms 25248 KB Output is correct
15 Runtime error 44 ms 40980 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -