Submission #331693

#	Time	Username	Problem	Language	Result	Execution time	Memory
331693		retsiger	Virus Experiment (JOI19_virus)	C++14	0 / 100	2072 ms	9068 KiB

virus

#include<bits/stdc++.h>
#define x first
#define y second
#define bug(x) cerr<<#x<<" = "<<x<<'\n'

using namespace std;

const int maxn = 1000, dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};

typedef pair<int, int> ii;

int M, R, C, Ans, Cnt;
int A[maxn][maxn], len[20];
string S;

bool in(int i, int j) {
  return (1 <= i && i <= R && 1 <= j && j <= C && A[i][j]);
}

int id(char ch) {
  if (ch == 'N') return 0;
  if (ch == 'E') return 1;
  if (ch == 'S') return 2;
  if (ch == 'W') return 3;
}

bool vis[maxn][maxn];
int cur[maxn][maxn];

int go(int i, int j) {
  memset(vis, 0, sizeof vis);
  memset(cur, 0, sizeof cur);
  queue<ii> q; vis[i][j] = 1;
  int tot = 0;
  q.push(ii(i, j));
  while (q.size()) {
    int u, v; tie(u, v) = q.front(); q.pop();
    //cerr<<u<<' '<<v<<'\n';
    ++tot;
    for (int i = 0; i < 4; ++i) {
      int nu = u + dx[i];
      int nv = v + dy[i];
      if (in(nu, nv) && !vis[nu][nv]) {
        cur[nu][nv] |= (1 << i);
        //cerr<<nu<<' '<<nv<<'\n';
        if (len[cur[nu][nv]] >= A[nu][nv]) {
          vis[nu][nv] = 1;
          q.push(ii(nu, nv));
        }
      }
    }
    //break;
  }
  return tot;
}

int main() {
//  freopen("virus.inp", "r", stdin);
//  freopen("virus.out", "w", stdout);
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> M >> R >> C >> S;
  S += S;
  for (int i = 1; i <= R; ++i) {
    for (int j = 1; j <= C; ++j) {
      cin >> A[i][j];
    }
  }
  ///0 - N
  ///1 - E
  ///2 - S
  ///3 - W
  for (int msk = 1; msk < 16; ++msk) {
    int l = -1;
    for (int i = 0; i < 2 * M; ++i) {
      if (!(msk >> id(S[i]) & 1)) {
        l = i;
      }
      len[msk] = max(len[msk], i - l);
    }
    len[msk] = min(len[msk], M);
  }
  Ans = R * C;
  for (int i = 1; i <= R; ++i) {
    for (int j = 1; j <= C; ++j) if (A[i][j]) {
      int v = go(i, j);
      //cerr<<i<<' '<<j<<'\n';
      //bug(v);
      //cerr<<'\n';
      if (v < Ans) {
        Ans = v;
        Cnt = 1;
      } else if (v == Ans) ++Cnt;
    }
  }
  cout << Ans << '\n' << Cnt << '\n';
  return 0;
}

Compilation message (stderr)

virus.cpp: In function 'int id(char)':
virus.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
   25 | }
      | ^

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