Submission #538960

#TimeUsernameProblemLanguageResultExecution timeMemory
538960MonarchuwuVirus Experiment (JOI19_virus)C++17
0 / 100
2077 ms4776 KiB
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 800 + 10;
const int dx[4] = { 0, 0, -1, 1 };
const int dy[4] = { -1, 1, 0, 0 };
int m, n, k;
int u[N][N];
char c[N << 1];

int op[256], cnt[16], ma[16];
void init() {
    op['E'] = 0, op['W'] = 1, op['S'] = 2, op['N'] = 3;
    copy(c, c + k, c + k);
    k <<= 1;
    for (int i = 1, x; i < k; ++i) {
        x = op[c[i]];
        for (int msk = 1; msk < 16; ++msk)
            if (msk >> x & 1)
                ma[msk] = max(ma[msk], ++cnt[msk]);
            else cnt[msk] = 0;
    }
}

bool vis[N][N];
bool check(int x, int y) {
    return 0 < x && x <= m && 0 < y && y <= n && u[x][y] && !vis[x][y];
}
int getmsk(int x, int y) {
    int msk = 0;
    for (int i = 0; i < 4; ++i) {
        int xx = x - dx[i], yy = y - dy[i];
        msk |= vis[xx][yy] << i;
    }
    return msk;
}
int calc(int x, int y) {
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) vis[i][j] = false;

    queue<pii> q;
    q.emplace(x, y);
    vis[x][y] = true;

    int cnt(0);
    while (!q.empty()) {
        pii tmp = q.front(); q.pop();
        ++cnt;

        for (int i = 0; i < 4; ++i) {
            x = tmp.ff + dx[i], y = tmp.ss + dy[i];
            if (!check(x, y)) continue;

            int msk = getmsk(x, y);
            if (ma[msk] >= u[x][y]) {
                vis[x][y] = true;
                q.emplace(x, y);
            }
        }
    }
    return cnt;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> k >> m >> n >> c;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) cin >> u[i][j];
    init();

    int mi(m * n + 1), cnt(0);
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) if (u[i][j]) {
            int x = calc(i, j);
            if (mi > x) mi = x, cnt = 1;
            else if (mi == x) ++cnt;
        }
    cout << mi << ' ' << cnt << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Compilation message (stderr)

virus.cpp: In function 'void init()':
virus.cpp:24:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |         x = op[c[i]];
      |                ~~~^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...