oj.uz

답안 #818972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
818972 2023-08-10T07:29:48 Z 이성호(#10133) 바이러스 (JOI19_virus) C++17
0 / 100
 2 ms 980 KB 
#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
int cnt[16];
bool inc(char c, int pv)
{
    if (c == 'W') return pv >> 1 & 1;
    else return pv >> 3 & 1;
}
bool infected[805][805];
int arr[805][805];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int M, R, C; cin >> M >> R >> C;
    string D; cin >> D; D += D;
    for (int i = 0; i < 16; i++) {
        if (i & 1 || i >> 2 & 1) continue;
        for (int j = 0; j < 2*M; j++) {
            if (!inc(D[j], i)) continue;
            int s = j;
            while (j + 1 < 2*M && inc(D[j+1], i)) j++;
            int e = j;
            cnt[i] = max(cnt[i], e - s + 1);
        }
        if (cnt[i] >= M) cnt[i] = 100000;
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 0) arr[i][j] = 200001;
        }
    }
    auto chk = [&](int i, int j){return 0 <= i && i < R && 0 <= j && j < C;};
    auto state = [&](int i, int j)
    {
        int ans = 0;
        if (chk(i, j-1)) ans |= (int)infected[i][j-1] << 1;
        if (chk(i, j+1)) ans |= (int)infected[i][j+1] << 3;
        return ans;
    };
    int mn = R * C + 1, mncnt = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (arr[i][j] == 200001) continue;
            vector<pair<int, int>> roll;
            infected[i][j] = true;
            queue<pair<int, int>> q; q.push(make_pair(i, j));
            int dx[] = {0, 0};
            int dy[] = {-1, 1};
            while (!q.empty()) {
                int x = q.front().first, y = q.front().second;
                roll.push_back(make_pair(x, y));
                q.pop();
                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k], ny = y + dy[k];
                    if (!chk(nx, ny) || infected[nx][ny]) continue;
                    if (cnt[state(nx, ny)] >= arr[nx][ny]) {
                        infected[nx][ny] = true;
                        q.push(make_pair(nx, ny));
                    }
                }
            }
            if (mn > (int)roll.size()) {
                mn = (int)roll.size();
                mncnt = 1;
            }
            else if (mn == (int)roll.size()) {
                mncnt++;
            }
            for (pair<int, int> p:roll) infected[p.first][p.second] = false;
        }
    }
    cout << mn << '\n';
    cout << mncnt << '\n';
    return 0;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -