제출 #1325149

#제출 시각아이디문제언어결과실행 시간메모리
1325149zwezdinv바이러스 (JOI19_virus)C++20
100 / 100
714 ms142228 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;
        }
    }
    std::vector num(n, std::vector<int>(m));
    int c = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (u[i][j]) num[i][j] = c++;
        }
    }
    int ans = n * m + 1, cans = 0;
    int iter = 0;
    while (true) {
        assert(++iter <= 40);
        std::vector<std::vector<int>> adj(c), radj(c);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (!u[i][j]) continue;
                std::map<int, int> mp;
                for (int c = 0; c < 4; ++c) {
                    int x = i - dir[c].first, y = j - dir[c].second;
                    if (0 <= x && x < n && 0 <= y && y < m && u[x][y] && num[x][y] != num[i][j]) {
                        mp[num[x][y]] |= 1 << c;
                    }
                }
                for (auto [c, mask] : mp) {
                    if (mx[mask] >= u[i][j]) {
                        adj[c].push_back(num[i][j]);
                        radj[num[i][j]].push_back(c);
                    }
                }
            }
        }
        std::vector<int> used(c), topsort;
        for (int i = 1; i < c; ++i) {
            if (!used[i]) {
                auto dfs = [&](auto dfs, int u) -> void {
                    used[u] = true;
                    for (auto to : adj[u]) {
                        if (!used[to]) dfs(dfs, to);
                    }
                    topsort.push_back(u);
                };
                dfs(dfs, i);
            }
        }
        std::reverse(topsort.begin(), topsort.end());
        std::fill(used.begin(), used.end(), 0);
        int nc = 1;
        std::vector<bool> ok(c);
        for (auto i : topsort) {
            if (!used[i]) {
                auto dfs = [&](auto dfs, int u) -> void {
                    used[u] = nc;
                    for (auto to : radj[u]) {
                        if (!used[to]) dfs(dfs, to);
                    }
                };
                dfs(dfs, i);
                nc++;
            }
        }
        std::vector<bool> out(nc);
        for (int i = 1; i < c; ++i) {
            for (auto j : adj[i]) {
                if (used[i] != used[j]) out[used[i]] = true;
            }
        }
        std::vector<int> sz(nc);
        std::vector nnum(n, std::vector<int>(m));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (u[i][j]) {
                    nnum[i][j] = used[num[i][j]];
                    sz[nnum[i][j]]++;
                }
            }
        }
        ans = n * m + 1, cans = 0;
        for (int i = 1; i < nc; ++i) {
            if (!out[i]) {
                if (sz[i] < ans) ans = sz[i], cans = 0;
                if (sz[i] == ans) cans += sz[i];
            }
        }
        std::vector<int> mt(nc);
        bool rem = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (!u[i][j]) continue;
                if (!mt[nnum[i][j]]) {
                    mt[nnum[i][j]] = num[i][j];
                }
                rem &= mt[nnum[i][j]] == num[i][j];
            }
        }
        if (rem) break;
        num = nnum, c = nc;
    }
    std::cout << ans << ' ' << cans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...