제출 #1325136

#제출 시각아이디문제언어결과실행 시간메모리
1325136zwezdinvVirus Experiment (JOI19_virus)C++20
6 / 100
2094 ms10524 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));
    auto relax = [&](int x, int y) -> void {
        int cur = 0;
        timer++;
        std::queue<std::pair<int, int>> que;
        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;
    };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (!u[i][j]) continue;
            relax(i, j);
        }
    }
    std::cout << ans << ' ' << cans;
    // 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]) {
    //             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] <= 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;
    //     auto dfs = [&](auto dfs, int x, int y) -> void {
    //         used[x][y] = c;
    //         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[x][y] <= mx[1 << c] && !used[i][j]) {
    //                 dfs(dfs, i, j);
    //             }
    //         }
    //     };
    //     ++c;
    //     dfs(dfs, x, y);
    // }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...