Submission #681876

#	Time	Username	Problem	Language	Result	Execution time	Memory
681876		nutella	Virus Experiment (JOI19_virus)	C++17	0 / 100	477 ms	65600 KiB

virus

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

constexpr int dx[]{-1, 0, 1, 0}, dy[]{0, 1, 0, -1};

struct DSU {
    vector<int> p, sz;
    vector<vector<int>> subtree;

    DSU() = default;

    DSU(int n) : p(n), sz(n, 1), subtree(n) {
        iota(p.begin(), p.end(), 0);
        for (int i = 0; i < n; ++i) {
            subtree[i] = {i};
        }
    }

    int leader(int x) {
        return x == p[x] ? x : p[x] = leader(p[x]);
    }

    bool unite(int a, int b) {
        a = leader(a), b = leader(b);
        if (a == b) {
            return false;
        }
        if (sz[a] < sz[b]) {
            swap(a, b);
        }

        subtree[a].insert(subtree[a].end(), subtree[b].begin(), subtree[b].end());
        subtree[b].clear();

        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M, n, m;
    cin >> M >> n >> m;

    string str;
    cin >> str;

    vector<int> s(M);
    for (int i = 0; i < M; ++i) {
        char c = str[i];
        s[i] = c == 'N' ? 0 : c == 'E' ? 1 : c == 'S' ? 2 : 3;
    }

    vector u(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> u[i][j];
        }
    }

    const int N = n * m;

    vector dead(16, vector(n, vector<bool>(m)));
    for (int mask = 1; mask < 16; ++mask) {
        vector<bool> yay(M);

        for (int i = 0; i < M; ++i) {
            if (mask >> s[i] & 1) {
                yay[i] = true;
            }
        }

        int mx = 0;
        int first = -1e9, last = -1e9;
        for (int i = 0, j = 0; i < M; i = j) {
            while (j < M && yay[i] == yay[j]) {
                j += 1;
            }

            if (yay[i]) {
                mx = max(mx, j - i);
                if (i == 0) {
                    first = j - i;
                } else if (j == M) {
                    last = j - i;
                }
            }
        }

        mx = max(mx, first + last);

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                dead[mask][i][j] = u[i][j] && u[i][j] <= mx;
            }
        }
    }

    DSU d(N);

    auto leader = [&](int i, int j) {
        return d.leader(i * m + j);
    };

    auto check = [&](int i, int j, int a) -> bool {
        int mask = 0;
        for (int k = 0; k < 4; ++k) {
            int ni = i + dx[k], nj = j + dy[k];
            if (ni >= 0 && ni < n && nj >= 0 && nj < m && leader(ni, nj) == a) {
                mask |= 1 << k;
            }
        }
        return dead[mask][i][j];
    };

    auto mrg = [&](vector<int> &fi, vector<int> &se) {
        bool swapped = false;
        if (fi.size() < se.size()) {
            swapped = true;
            swap(fi, se);
        }

        for (int x: se) {
            fi.push_back(x);
        }

        se.clear();
        if (swapped) {
            swap(fi, se);
        }
    };

    int ans = numeric_limits<int>::max();
    int cnt = 0;

    vector<bool> in_stk(N);
    vector was(n, vector<bool>(m));

    for (int ii = 0; ii < n; ++ii) {
        for (int jj = 0; jj < m; ++jj) {
            if (was[ii][jj]) {
                continue;
            }

            vector<int> stk;
            vector<vector<int>> vst;

            int i = ii, j = jj;
            vst.push_back({i * m + j});
            stk.push_back({i * m + j});
            was[i][j] = true;
            in_stk[i * m + j] = true;

            bool ok = true;
            while (!vst.back().empty()) {
                const int now = vst.back().back();

                int x = now / m, y = now % m;

                bool same = true;
                for (int k = 0; k < 4; ++k) {
                    int nx = x + dx[k], ny = y + dy[k];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                        const int to = nx * m + ny;

                        if (d.leader(to) == d.leader(now)) {
                            continue;
                        }

                        if (check(nx, ny, leader(i, j))) {
                            int ld = d.leader(nx * m + ny);
                            if (in_stk[ld]) {
                                vector<int> &nxt = vst.back();
                                nxt.push_back(now);

                                int pnt = vst.size() - 1;
                                for (; pnt >= 0; --pnt) {
                                    if (stk[pnt] == ld) {
                                        break;
                                    }
                                }

                                pair<int, int> mx = {-1, -1};
                                for (int aa = pnt; aa < vst.size() - 1; ++aa) {
//                                    mx = max(mx, pair{int(d.subtree[d.leader(stk[aa])].size()), aa});
                                    mrg(nxt, vst[aa]);
                                }

                                for (int aa = pnt; aa < vst.size(); ++aa) {
                                    if (aa != mx.second) {
                                        for (int yy : d.subtree[d.leader(stk[aa])]) {
                                            nxt.push_back(yy);
                                        }
                                    }
                                }

                                for (int aa = pnt; aa < vst.size() - 1; ++aa) {
                                    d.unite(stk[aa], now);
                                }

                                swap(nxt, vst[pnt]);

                                for (int aa = pnt; aa < stk.size(); ++aa) {
                                    in_stk[stk[aa]] = false;
                                }

                                vst.resize(pnt + 1);
                                stk.resize(pnt + 1);

                                int lead = d.leader(i * m + j);
                                assert(!in_stk[lead]);

                                i = lead / m, j = lead % m;

                                in_stk[lead] = true;

                                stk[pnt] = lead;

                                same = false;
                                break;
                            } else if (was[nx][ny]) {
                                ok = false;
                                goto endr;
                            } else {
                                vst.push_back({nx * m + ny});
                                stk.push_back(nx * m + ny);

                                i = nx, j = ny;
                                was[i][j] = true;
                                in_stk[i * m + j] = true;

                                same = false;
                                break;
                            }
                        }
                    }
                }
                if (same) {
                    vst.back().pop_back();
                }
            }
            endr:;

            int lead = d.leader(i * m + j);
            assert(lead == i * m + j);

            if (ok) {
                int now = d.subtree[lead].size();
                if (ans > now) {
                    ans = now;
                    cnt = now;
                } else if (ans == now) {
                    cnt += now;
                }
            }
            for (int aa: stk) {
                in_stk[aa] = false;
            }
        }
    }

    cout << ans << '\n' << cnt << '\n';

    return 0;
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:190:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx1998::vector<std::__debug::vector<int>, std::allocator<std::__debug::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |                                 for (int aa = pnt; aa < vst.size() - 1; ++aa) {
      |                                                    ~~~^~~~~~~~~~~~~~~~
virus.cpp:195:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx1998::vector<std::__debug::vector<int>, std::allocator<std::__debug::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |                                 for (int aa = pnt; aa < vst.size(); ++aa) {
      |                                                    ~~~^~~~~~~~~~~~
virus.cpp:203:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx1998::vector<std::__debug::vector<int>, std::allocator<std::__debug::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |                                 for (int aa = pnt; aa < vst.size() - 1; ++aa) {
      |                                                    ~~~^~~~~~~~~~~~~~~~
virus.cpp:209:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx1998::vector<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |                                 for (int aa = pnt; aa < stk.size(); ++aa) {
      |                                                    ~~~^~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 6
• Subtask 3: 0 / 80