Submission #434006

#	Time	Username	Problem	Language	Result	Execution time	Memory
434006		dxz05	Virus Experiment (JOI19_virus)	C++14	0 / 100	23 ms	840 KiB

virus

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 55;

#define MP make_pair
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int n, m;
int a[N][N];

int arr[20];
int code[256];

bool ill[N][N];
int virus(int I, int J){
    memset(ill, 0, sizeof(ill));
    ill[I][J] = true;

    queue<pair<int, int>> q;
    q.push(MP(I - 1, J));
    q.push(MP(I, J - 1));
    q.push(MP(I + 1, J));
    q.push(MP(I, J + 1));

    int it = 500;
    while (!q.empty() && it--){
        int i = q.front().first, j = q.front().second;
        //cout << i << ' ' << j << endl;
        q.pop();
        if (ill[i][j] || a[i][j] == 0) continue;

        int mask = 0;
        if (ill[i - 1][j]) mask |= 1;
        if (ill[i][j + 1]) mask |= 2;
        if (ill[i + 1][j]) mask |= 4;
        if (ill[i][j - 1]) mask |= 8;

        if (arr[mask] >= a[i][j]) ill[i][j] = true;

        q.push(MP(i - 1, j));
        q.push(MP(i, j - 1));
        q.push(MP(i + 1, j));
        q.push(MP(i, j + 1));

    }

    //cout << I << ' ' << J << endl;

    int res = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            res += ill[i][j];
         //   cout << ill[i][j] << ' ';
        }
       // cout << endl;
    }

    return res;
}

void solve(){
    int len; string s;
    cin >> len >> n >> m >> s;

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }

    s += s;
    len <<= 1;

    code['N'] = 1, code['E'] = 2, code['S'] = 4, code['W'] = 8;

    for (int mask = 1; mask < 16; mask++){
        for (int i = 0; i < len; i++){
            if (!(mask & code[s[i]])) continue;
            int j = i;
            while (j < len && (mask & code[s[j]])) j++;
            j--;
            arr[mask] = max(arr[mask], j - i + 1);
            i = j;
        }
        if (arr[mask] == len) arr[mask] = 1e9;
       // cout << (bitset<4>(mask)) << ' ';
       // cout << arr[mask] << endl;
    }

    int ans = 1e9, cnt = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (a[i][j] == 0) continue;
            int cur = virus(i, j);
            if (cur < ans){
                ans = cur;
                cnt = 1;
            } else if (cur == ans) cnt++;
        }
    }

    cout << ans << endl << cnt << endl;

}

int main(){
    ios_base::sync_with_stdio(false);
    //freopen("output.txt", "w", stdout);
    int tests = 1;
   // cin >> tests;

    while (tests--){
        solve();
    }

    return 0;
}

Compilation message (stderr)

virus.cpp: In function 'void solve()':
virus.cpp:82:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   82 |             if (!(mask & code[s[i]])) continue;
      |                                   ^
virus.cpp:84:48: warning: array subscript has type 'char' [-Wchar-subscripts]
   84 |             while (j < len && (mask & code[s[j]])) j++;
      |                                                ^

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