oj.uz

Submission #818941

# Submission time Handle Problem Language Result Execution time Memory
818941 2023-08-10T07:24:21 Z 이성호(#10133) Virus Experiment (JOI19_virus) C++17
6 / 100
 2000 ms 3352 KB 
#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
//N: 0, W: 1, S: 2, E: 3
int cnt[16];
bool inc(char c, int pv)
{
    if (c == 'N') return pv >> 0 & 1;
    else if (c == 'W') return pv >> 1 & 1;
    else if (c == 'S') return pv >> 2 & 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++) {
        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-1, j)) ans |= (int)infected[i-1][j] << 0;
        if (chk(i, j-1)) ans |= (int)infected[i][j-1] << 1;
        if (chk(i+1, j)) ans |= (int)infected[i+1][j] << 2;
        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[] = {-1, 0, 1, 0};
            int dy[] = {0, -1, 0, 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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 576 KB Output is correct
2 Correct 147 ms 3352 KB Output is correct
3 Execution timed out 2085 ms 2988 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 23 ms 752 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 21 ms 724 KB Output is correct
6 Correct 156 ms 780 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 21 ms 788 KB Output is correct
9 Correct 72 ms 528 KB Output is correct
10 Correct 5 ms 724 KB Output is correct
11 Correct 4 ms 532 KB Output is correct
12 Correct 197 ms 552 KB Output is correct
13 Correct 92 ms 752 KB Output is correct
14 Correct 93 ms 784 KB Output is correct
15 Correct 88 ms 760 KB Output is correct
16 Correct 82 ms 832 KB Output is correct
17 Correct 12 ms 632 KB Output is correct
18 Correct 8 ms 520 KB Output is correct
19 Correct 22 ms 760 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 576 KB Output is correct
2 Correct 147 ms 3352 KB Output is correct
3 Execution timed out 2085 ms 2988 KB Time limit exceeded
4 Halted 0 ms 0 KB -