제출 #681899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681899		nutella	바이러스 (JOI19_virus)	C++17	100 / 100	364 ms	56516 KiB

virus

#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);
        if (mx == M) {
            mx = numeric_limits<int>::max();
        }

        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 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 && d.leader(ni * m + nj) == a) {
                mask |= 1 << k;
            }
        }
        return dead[mask][i][j];
    };

    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] || u[ii][jj] == 0) {
                continue;
            }

            vector<int> stk;
            vector<vector<int>> consider;
            
            int i = ii, j = jj;

            consider.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 (!consider.back().empty()) {
                const int now = consider.back().back();

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

                bool pop = 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, i * m + j)) {
                            int lead = d.leader(nx * m + ny);
                            
                            if (in_stk[lead]) {
                                int pnt = consider.size() - 1;
                                for (; pnt >= 0; --pnt) {
                                    if (stk[pnt] == lead) {
                                        break;
                                    }
                                }

                                for (int p = pnt + 1; p < consider.size(); ++p) {
                                    if (consider[pnt].size() < consider[p].size()) {
                                        swap(consider[pnt], consider[p]);
                                    }
                                    for (int yy : consider[p]) {
                                        consider[pnt].push_back(yy);
                                    }
                                }

                                pair<int, int> mx = {-1, -1};
                                for (int p = pnt; p < stk.size(); ++p) {
                                    mx = max(mx, pair{int(d.subtree[stk[p]].size()), p});
                                }
                                
                                for (int p = pnt; p < consider.size(); ++p) {
                                    if (p != mx.second) {
                                        for (int yy: d.subtree[stk[p]]) {
                                            consider[pnt].push_back(yy);
                                        }
                                    }
                                }

                                for (int aa = pnt; aa < consider.size() - 1; ++aa) {
                                    d.unite(stk[aa], i * m + j);
                                }

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

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

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

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

                                in_stk[lead] = true;

                                stk[pnt] = lead;

                                pop = false;
                                break;
                            } else if (was[nx][ny]) {
                                ok = false;
                                break;
                            } else {
                                consider.push_back(vector{nx * m + ny});
                                stk.push_back(nx * m + ny);

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

                                pop = false;
                                break;
                            }
                        }
                    }
                }
                if (!ok) {
                    break;
                }
                if (pop) {
                    consider.back().pop_back();
                }
            }

            int lead = d.leader(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;
}

컴파일 시 표준 에러 (stderr) 메시지

virus.cpp: In function 'int main()':
virus.cpp:169:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |                                 for (int p = pnt + 1; p < consider.size(); ++p) {
      |                                                       ~~^~~~~~~~~~~~~~~~~
virus.cpp:179:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |                                 for (int p = pnt; p < stk.size(); ++p) {
      |                                                   ~~^~~~~~~~~~~~
virus.cpp:183:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |                                 for (int p = pnt; p < consider.size(); ++p) {
      |                                                   ~~^~~~~~~~~~~~~~~~~
virus.cpp:191:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |                                 for (int aa = pnt; aa < consider.size() - 1; ++aa) {
      |                                                    ~~~^~~~~~~~~~~~~~~~~~~~~
virus.cpp:195:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |                                 for (int aa = pnt; aa < stk.size(); ++aa) {
      |                                                    ~~~^~~~~~~~~~~~

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