oj.uz

Submission #547670

# Submission time Handle Problem Language Result Execution time Memory
547670 2022-04-11T10:17:14 Z Lam_lai_cuoc_doi Raspad (COI17_raspad) C++17
26 / 100
 233 ms 42052 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];
    vector<pair<int, int>> snap;

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

    int findpar(int v)
    {
        while (par[v] > 0)
            v = par[v];
        return 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);

        snap.emplace_back(u, par[u]);
        par[v] += par[u];
        par[u] = v;

        return true;
    }

    void RollBack(int sz)
    {
        while ((int)snap.size() > sz)
        {
            pair<int, int> c = snap.back();
            snap.pop_back();

            par[par[c.first]] -= c.second;
            par[c.first] = c.second;
        }
    }
} 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;

    g.RollBack(0);

    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]));
        }
    }

    f.RollBack(0);

    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:226:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
raspad.cpp:227:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  227 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 6 ms 11420 KB Output is correct
3 Correct 5 ms 11424 KB Output is correct
4 Correct 5 ms 11348 KB Output is correct
5 Correct 5 ms 11300 KB Output is correct
6 Correct 5 ms 11420 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 6 ms 11420 KB Output is correct
3 Correct 5 ms 11424 KB Output is correct
4 Correct 5 ms 11348 KB Output is correct
5 Correct 5 ms 11300 KB Output is correct
6 Correct 5 ms 11420 KB Output is correct
7 Correct 12 ms 11860 KB Output is correct
8 Correct 5 ms 11364 KB Output is correct
9 Correct 22 ms 12212 KB Output is correct
10 Correct 11 ms 11984 KB Output is correct
11 Correct 19 ms 12112 KB Output is correct
12 Correct 12 ms 11860 KB Output is correct
13 Correct 16 ms 11984 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 30932 KB Output is correct
2 Runtime error 40 ms 42052 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 5 ms 11220 KB Output is correct
2 Correct 6 ms 11420 KB Output is correct
3 Correct 5 ms 11424 KB Output is correct
4 Correct 5 ms 11348 KB Output is correct
5 Correct 5 ms 11300 KB Output is correct
6 Correct 5 ms 11420 KB Output is correct
7 Correct 12 ms 11860 KB Output is correct
8 Correct 5 ms 11364 KB Output is correct
9 Correct 22 ms 12212 KB Output is correct
10 Correct 11 ms 11984 KB Output is correct
11 Correct 19 ms 12112 KB Output is correct
12 Correct 12 ms 11860 KB Output is correct
13 Correct 16 ms 11984 KB Output is correct
14 Correct 233 ms 30932 KB Output is correct
15 Runtime error 40 ms 42052 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -