Submission #1270053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270053		MisterReaper	Virus Experiment (JOI19_virus)	C++20	100 / 100	354 ms	21424 KiB

virus

// File A.cpp created on 14.09.2025 at 23:55:33
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

struct DSU {
    std::vector<int> f, siz;
    DSU(int n) : f(n), siz(n, 1) {
        std::iota(f.begin(), f.end(), 0);
    }
    void init(int n) {
        f.assign(n, 0);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    int get(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b) {
            return false;
        } else if (siz[a] > siz[b]) {
            std::swap(a, b);
        }
        f[a] = b;
        siz[b] += siz[a];
        return true;
    }
    bool same(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return siz[get(x)];
    }
};

std::string dirs = "NESW";
constexpr int dx[] = {-1, 0, +1, 0};
constexpr int dy[] = {0, +1, 0, -1};

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

    int N, R, C;
    std::cin >> N >> R >> C;

    std::string S;
    std::cin >> S;

    std::vector<std::vector<int>> U(R, std::vector<int>(C));
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            std::cin >> U[i][j];
        }
    }

    N += N;
    S += S;

    std::vector<int> mx(1 << 4);
    for (int m = 0; m < (1 << 4); ++m) {
        for (int i = 0, j = 0; i < N; i = j) {
            if (~m >> dirs.find(S[i]) & 1) {
                j++;
                continue;
            }
            while (j < N && m >> dirs.find(S[j]) & 1) {
                j++;
            }
            if (i == 0 && j == N) {
                mx[m] = std::max(mx[m], int(1E9));
            } else {
                mx[m] = std::max(mx[m], j - i);
            }
        }
    }

    debug(mx);

    int viscnt = 0;
    DSU dsu(R * C);
    std::vector<int> is_root(R * C), vis(R * C);
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (U[i][j] != 0) {
                is_root[i * C + j] = true;
            }
        }
    }

    std::queue<int> que;
    auto bfs = [&](int v, int tp) -> int {
        while (!que.empty()) {
            que.pop();
        }

        int siz = 0;
        que.emplace(v);
        vis[v] = ++viscnt;
        while (!que.empty()) {
            auto u = que.front();
            que.pop();
            siz++;
            int x = u / C;
            int y = u % C;
            for (int d = 0; d < 4; ++d) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (nx < 0 || nx >= R || ny < 0 || ny >= C || U[nx][ny] == 0 || vis[nx * C + ny] == viscnt) {
                    continue;
                }
                int msk = 0;
                for (int nd = 0; nd < 4; ++nd) {
                    int nnx = nx + dx[nd];
                    int nny = ny + dy[nd];
                    if (0 <= nnx && nnx < R && 0 <= nny && nny < C && vis[nnx * C + nny] == viscnt) {
                        msk |= 1 << nd;
                    }
                }
                if (mx[msk] >= U[nx][ny]) {
                    vis[nx * C + ny] = viscnt;
                    que.emplace(nx * C + ny);
                    if (tp == 0 && is_root[nx * C + ny]) {
                        return nx * C + ny;
                    }
                }
            }
        }
        if (tp == 0) {
            return -1;
        } else {
            return siz;
        }
    };

    std::vector<std::pair<int, int>> edg;

    while (true) {
        edg.clear();
        bool fl = false;
        for (int i = 0; i < R * C; ++i) {
            if (is_root[i]) {
                int p = bfs(i, 0);
                if (p != -1) {
                    edg.emplace_back(i, p);
                }
            }
        }
        for (auto[x, y] : edg) {
            if (!dsu.same(x, y)) {
                dsu.unite(x, y);
                is_root[x] = false;
                fl = true;
            }
        }
        if (!fl) {
            break;
        }
    }

    std::pair<int, int> ans = {R * C, 0};

    for (int i = 0; i < R * C; ++i) {
        if (is_root[i]) {
            int sz = bfs(i, 1);
            debug(i, sz);
            if (ans.first > sz) {
                ans = {sz, sz};
            } else if (ans.first == sz) {
                ans.second += sz;
            }
        }
    }

    std::cout << ans.first << '\n' << ans.second << '\n';

    return 0;
}

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