Submission #1325139

#TimeUsernameProblemLanguageResultExecution timeMemory
1325139zwezdinv바이러스 (JOI19_virus)C++20
6 / 100
2096 ms21512 KiB
#include<bits/stdc++.h>

std::string d = "NSWE";
std::vector<std::pair<int, int>> dir = {{
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}
}};

int reverse(int mask) {
    int ret = 0;
    for (int i = 0; i < 4; ++i) {
        ret |= (mask >> i & 1) << (i ^ 1);
    }
    return ret;
}

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

    int k, n, m;
    std::cin >> k >> n >> m;
    std::string sss;
    std::cin >> sss;
    std::vector<int> mx(1 << 4, 0);
    for (int mask = 0; mask < 1 << 4; ++mask) {
        std::vector<int> a(k);
        for (int i = 0; i < k; ++i) {
            int c = std::find(d.begin(), d.end(), sss[i]) - d.begin();
            a[i] = mask >> c & 1;
        }
        if (std::count(a.begin(), a.end(), 1) == k) {
            mx[mask] = 1e9;
        } else {
            std::rotate(a.begin(), std::find(a.begin(), a.end(), 0), a.end());
            for (int i = 0; i < k; ++i) {
                if (!a[i]) continue;
                int j = i;
                while (j < k && a[j]) ++j;
                mx[mask] = std::max(mx[mask], j - i);
                i = j;
            }
        }
    }
    std::vector u(n, std::vector<int>(m));
    for (auto& i : u) {
        for (auto& j : i) {
            std::cin >> j;
        }
    }
    int ans = n * m + 1, cans = 0;
    int timer = 0;
    std::vector<std::vector<int>> tim(n, std::vector<int>(m));
    std::vector<std::vector<int>> infect(n, std::vector<int>(m));
    std::vector<std::vector<int>> mask(n, std::vector<int>(m));
    std::queue<std::pair<int, int>> que;
    auto relax = [&](int x, int y, int c) -> void {
        int cur = 0;
        timer++;
        que.emplace(x, y);
        tim[x][y] = timer, infect[x][y] = 1;
        while (que.size()) {
            auto [x, y] = que.front();
            que.pop();
            ++cur;
            for (int c = 0; c < 4; ++c) {
                int i = x + dir[c].first, j = y + dir[c].second;
                if (i < 0 || i >= n || j < 0 || j >= m || !u[i][j]) continue;
                if (tim[i][j] != timer) {
                    tim[i][j] = timer, infect[i][j] = 0, mask[i][j] = 0;
                }
                if (infect[i][j]) continue;
                mask[i][j] |= 1 << c;
                if (mx[mask[i][j]] >= u[i][j]) {
                    infect[i][j] = 1;
                    que.emplace(i, j);
                }
            }
        }
        if (cur < ans) ans = cur, cans = 0;
        if (cur == ans) cans += c;
    };
    std::vector used(n, std::vector<int>(m));
    std::vector<std::pair<int, int>> topsort;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (!used[i][j] && u[i][j]) {
                auto dfs = [&](auto dfs, int x, int y) -> void {
                    used[x][y] = 1;
                    for (int c = 0; c < 4; ++c) {
                        int i = x + dir[c].first, j = y + dir[c].second;
                        if (0 <= i && i < n && 0 <= j && j < m && u[i][j] && u[i][j] <= mx[1 << c] && !used[i][j]) {
                            dfs(dfs, i, j);
                        }
                    }
                    topsort.emplace_back(x, y);
                };
                dfs(dfs, i, j);
            }
        }
    }
    used.assign(n, std::vector<int>(m, 0));
    std::reverse(topsort.begin(), topsort.end());
    int c = 0;
    for (auto [x, y] : topsort) {
        if (used[x][y]) continue;
        int cnt = 0;
        auto dfs = [&](auto dfs, int x, int y) -> void {
            used[x][y] = c;
            ++cnt;
            for (int c = 0; c < 4; ++c) {
                int i = x - dir[c].first, j = y - dir[c].second;
                if (0 <= i && i < n && 0 <= j && j < m && u[i][j] && u[x][y] <= mx[1 << c] && !used[i][j]) {
                    dfs(dfs, i, j);
                }
            }
        };
        ++c;
        dfs(dfs, x, y);
        relax(x, y, cnt);
    }
    std::cout << ans << ' ' << cans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...