Submission #504897

#	Time	Username	Problem	Language	Result	Execution time	Memory
504897		tengiz05	Virus Experiment (JOI19_virus)	C++17	100 / 100	1093 ms	15880 KiB

virus

#include <bits/stdc++.h>

using i64 = long long;

std::string dir = "NSWE";
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int k, n, m;
    std::cin >> k >> n >> m;
    
    std::string D;
    std::cin >> D;
    
    D += D;
    
    int mx[1 << 4] {};
    
    for (int b = 0; b < (1 << 4); b++) {
        for (int i = 0; i < 2 * k; ) {
            int j = i;
            while (j < 2 * k && (b >> dir.find(D[j]) & 1)) {
                j++;
            }
            mx[b] = std::max(mx[b], j - i);
            i = std::max(i + 1, j);
        }
        if (mx[b] == 2 * k) {
            mx[b] = 1E9;
        }
    }
    
    int a[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> a[i][j];
        }
    }
    
    auto good = [&](int x, int y) {
        return x >= 0 && y >= 0 && x < n && y < m;
    };
    
    std::vector<std::pair<int, int>> v;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            v.emplace_back(i, j);
        }
    }
    std::random_shuffle(v.begin(), v.end());
    
    int mn = 1E9;
    int ans = 0;
    
    bool done[n][m] {};
    bool vis[n][m] {};
    
    for (auto [x, y] : v) {
        if (a[x][y] == 0)
            continue;
        std::queue<std::pair<int, int>> q, rem;
        
        q.emplace(x, y);
        rem.emplace(x, y);
        vis[x][y] = true;
        int siz = 0;
        
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            siz++;
            
            if (done[x][y]) {
                siz = -1;
                break;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int mask = 0;
                if (!good(nx, ny) || a[nx][ny] == 0) {
                    continue;
                }
                for (int j = 0; j < 4; j++) {
                    int X = nx + dx[j];
                    int Y = ny + dy[j];
                    if (good(X, Y) && vis[X][Y]) {
                        mask |= 1 << j;
                    }
                }
                if (mx[mask] >= a[nx][ny] && !vis[nx][ny]) {
                    vis[nx][ny] = true;
                    q.emplace(nx, ny);
                    rem.emplace(nx, ny);
                }
            }
        }
        
        done[x][y] = true;
        
        while (!rem.empty()) {
            auto [x, y] = rem.front();
            rem.pop();
            vis[x][y] = false;
        }
        
        if (siz == -1) {
            continue;
        }
        if (siz < mn) {
            mn = siz;
            ans = 0;
        }
        if (siz == mn) {
            ans += siz;
        }
    }
    
    std::cout << mn << "\n" << ans << "\n";
    
    return 0;
}

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