Submission #677798

#	Time	Username	Problem	Language	Result	Execution time	Memory
677798		puppy	Virus Experiment (JOI19_virus)	C++17	6 / 100	222 ms	852 KiB

virus

#include <bits/stdc++.h>
using namespace std;
#define int long long

int conv(bool N, bool W, bool S, bool E)
{
    return 8 * N + 4 * W + 2 * S + E;
}

bool isin(char c, int p)
{
    if (c == 'E') {
        return (p & 1) ? true : false;
    }
    if (c == 'S') {
        return (p & 2) ? true : false;
    }
    if (c == 'W') {
        return (p & 4) ? true : false;
    }
    if (c == 'N') {
        return (p & 8) ? true : false;
    }
}
int lim[16];
int arr[55][55];
bool infected[55][55];
int M, R, C;
bool valid(int i, int j)
{
    return 0 <= i && i < R && 0 <= j && j < C;
}
bool isinfected(int i, int j)
{
    if (!valid(i, j)) return false;
    return infected[i][j];
}
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> M >> R >> C;
    string s; cin >> s; s = s + s;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> arr[i][j];
        }
    }
    //N, W, S, E 순
    for (int i = 0; i < 16; i++) {
        bool yes = true;
        for (int k = 0; k < M; k++) {
            if (!isin(s[k], i)) {
                yes = false;
                break;
            }
        }
        if (yes) lim[i] = 100001;
        for (int k = 0; k < 2 * M; k++) {
            if (!isin(s[k], i)) continue;
            int st = k;
            while (k < 2 * M - 1 && isin(s[k+1], i)) k++;
            int en = k;
            lim[i] = max(lim[i], en - st + 1);
        }
    }
    int ans = 1e9, anscnt = 0;
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            //(i, j) 시작
            if (arr[i][j] == 0) continue;
            int cnt = 0;
            queue<pair<int, int>> q;
            fill(&infected[0][0], &infected[54][55], false);
            infected[i][j] = true;
            q.push(make_pair(i, j));
            //ok[0]부터 E, S, W, N
            while (!q.empty()) {
                int x = q.front().first, y = q.front().second;
                q.pop();
                cnt++;
                //(x, y)가 감염됨
                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k], ny = y + dy[k];
                    if (!valid(nx, ny)) continue;
                    if (arr[nx][ny] == 0) continue;
                    if (infected[nx][ny]) continue;
                    int pv = 0;
                    if (isinfected(nx, ny + 1)) pv |= 1;
                    if (isinfected(nx, ny - 1)) pv |= 4;
                    if (isinfected(nx + 1, ny)) pv |= 2;
                    if (isinfected(nx - 1, ny)) pv |= 8;
                    if (arr[nx][ny] <= lim[pv]) {
                        infected[nx][ny] = true;
                        q.push(make_pair(nx, ny));
                    }
                }
            }
            if (ans > cnt) {
                ans = cnt;
                anscnt = 1;
            }
            else if (ans == cnt) {
                anscnt++;
            }
        }
    }
    cout << ans << '\n' << anscnt << '\n';
}

Compilation message (stderr)

virus.cpp: In function 'bool isin(char, long long int)':
virus.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
   24 | }
      | ^

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