Submission #336403

#TimeUsernameProblemLanguageResultExecution timeMemory
336403KoDVirus Experiment (JOI19_virus)C++17
0 / 100
732 ms6636 KiB
#include <bits/stdc++.h>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

template <class T>
using Vec = std::vector<T>;

constexpr i32 inf32 = (u32) ~0 >> 2;
constexpr i64 inf64 = (u64) ~0 >> 2;

constexpr isize dx[] = { 1, 0, -1, 0 };
constexpr isize dy[] = { 0, 1, 0, -1 };
constexpr char dir[] = { 'S', 'E', 'N', 'W' };

int main() {
    usize N, H, W;
    std::cin >> N >> H >> W;
    std::string S;
    std::cin >> S;
    Vec<Vec<usize>> grid(H, Vec<usize>(W));
    for (auto &v: grid) {
        for (auto &x: v) {
            std::cin >> x;
            if (x == 0) {
                x = (usize) -1;
            }
        }
    }
    if (H <= 50 && W <= 50) {
        S += S;
        S += 'X';
        std::array<usize, 16> cont{};
        for (usize set = 0; set < 16; ++set) {
            usize cnt = 0;
            for (const auto c: S) {
                bool ok = false;
                for (usize k = 0; k < 4; ++k) {
                    if (set >> k & 1) {
                        if (dir[k] == c) {
                            ok = true;
                        }
                    }
                }
                if (ok) {
                    cnt += 1;
                } 
                else {
                    cont[set] = std::max(cont[set], cnt);
                    cnt = 0;
                }
            }
        }
        usize ans = H * W + 1, num = 0;
        for (usize sx = 0; sx < H; ++sx) {
            for (usize sy = 0; sy < W; ++sy) {
                if (!(~grid[sx][sy])) {
                    continue;
                }
                Vec<Vec<bool>> used(H, Vec<bool>(W));
                std::queue<std::pair<usize, usize>> que;
                const auto push = [&](const usize i, const usize j) {
                    if (!used[i][j]) {
                        used[i][j] = true;
                        que.emplace(i, j);
                    }
                };
                const auto check = [&](const usize i, const usize j) {
                    if (!(~grid[i][j])) {
                        return false;
                    }
                    usize idx = 0;
                    for (usize k = 0; k < 4; ++k) {
                        const auto ni = (isize) i + dx[k];
                        const auto nj = (isize) j + dy[k];
                        if (ni >= 0 && nj >= 0 && ni < (isize) H && nj < (isize) W) {
                            if (used[ni][nj]) {
                                idx ^= (1 << k);
                            }
                        }
                    }
                    return cont[idx] >= grid[i][j];
                };
                push(sx, sy);
                usize cnt = 0;
                while (!que.empty()) {
                    cnt += 1;
                    const auto [i, j] = que.front();
                    que.pop();
                    for (usize k = 0; k < 4; ++k) {
                        const auto ni = (isize) i + dx[k];
                        const auto nj = (isize) j + dy[k];
                        if (ni >= 0 && nj >= 0 && ni < (isize) H && nj < (isize) W) {
                            if (check(ni, nj)) {
                                push(ni, nj);
                            }
                        }
                    }
                }
                if (ans > cnt) {
                    ans = cnt;
                    num = 0;
                }
                if (ans == cnt) {
                    num += 1;
                }
            }
        }
        std::cout << ans << '\n';
        std::cout << num << '\n';
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...