Submission #538971

#	Time	Username	Problem	Language	Result	Execution time	Memory
538971		Monarchuwu	Virus Experiment (JOI19_virus)	C++17	20 / 100	300 ms	6668 KiB

virus

#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, K = 1e5 + 9;
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[K << 1];

int op[256], cnt[16], ma[16];
void init() {
    op['E'] = 0, op['W'] = 1, op['S'] = 2, op['N'] = 3;
    while (k < K) {
        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) {
    if (m <= 50 && n <= 50)
        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;
}
void subtask2() {
    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';
}

int l[N], r[N];
void subtask1() {
    int mi(n + 1), _cnt(0);
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j)
            l[j] = !u[i][j] ? 0 : ma[1] >= u[i][j - 1] ? l[j - 1] + 1 : 1;
        for (int j = n; j; --j)
            r[j] = !u[i][j] ? 0 : ma[2] >= u[i][j + 1] ? r[j + 1] + 1 : 1;

        for (int j = 1; j <= n; ++j) if (u[i][j]) {
            int len = l[j] + r[j] - 1;
            if (mi > len) mi = len, _cnt = 1;
            else if (mi == len) ++_cnt;
        }
    }
    cout << mi << ' ' << _cnt << '\n';
}

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();

    if (m <= 50 && n <= 50)
        subtask2();
    else subtask1();
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Compilation message (stderr)

virus.cpp: In function 'void init()':
virus.cpp:26:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   26 |         x = op[c[i]];
      |                ~~~^

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