oj.uz

Submission #331691

# Submission time Handle Problem Language Result Execution time Memory
331691 2020-11-29T15:15:08 Z retsiger Virus Experiment (JOI19_virus) C++14
0 / 100
 2000 ms 9708 KB 
#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) {
      int v = go(i, j);
      if (v < Ans) {
        Ans = v;
        Cnt = 1;
      } else if (v == Ans) ++Cnt;
    }
  }
  cout << Ans << '\n' << Cnt << '\n';
  return 0;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 5608 KB Output is correct
2 Execution timed out 2081 ms 9708 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 5356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 5608 KB Output is correct
2 Execution timed out 2081 ms 9708 KB Time limit exceeded
3 Halted 0 ms 0 KB -