Submission #495648

#	Time	Username	Problem	Language	Result	Execution time	Memory
495648		600Mihnea	Virus Experiment (JOI19_virus)	C++17	100 / 100	724 ms	25264 KiB

virus

#include <bits/stdc++.h>

using namespace std;

int Transform(int x) {
  return x;
}

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

mt19937 rng((long long) (new char));

const int M = 100000 + 7;
const int N = 800 + 7;
const int INF = (int) 1e9 + 7;
int mod;
int n;
int m;
string wind;
int res[N][N], mx[1 << 4], cur[1 << 4], when[N][N];
bool valid[N][N];

int dr[] = {-1, 0, 1, 0};
int dc[] = {0, -1, 0, 1};

bool isOk(int r, int c) {
  if (min(r, c) < 1 || r > n || c > m) {
    return false;
  }
  if (res[r][c] == 0) {
    return false;
  }
  int whosValid = 0;
  for (int k = 0; k < 4; k++) {
    int rn = r + dr[k], cn = c + dc[k];
    if (valid[rn][cn]) {
      whosValid += (1 << k);
    }
  }
  return mx[whosValid] >= res[r][c];
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  cin >> mod >> n >> m >> wind;

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

  wind += wind;

  for (auto &ch : wind) {
    int current = codif(ch);
    for (int mask = 0; mask < (1 << 4); mask++) {
      if (mask & (1 << current)) {
        cur[mask]++;
        mx[mask] = max(mx[mask], cur[mask]);
      } else {
        cur[mask] = 0;
      }
    }
  }

  for (int mask = 0; mask < (1 << 4); mask++) {
    if (mx[mask] >= mod) {
      mx[mask] = INF;
    }
  }


  vector<pair<int, int>> ord;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (res[i][j]) {
        ord.push_back({i, j});
      }
    }
  }

  shuffle(ord.begin(), ord.end(), rng);


  int y = 0;
  for (auto &it : ord) {
    when[it.first][it.second] = ++y;
  }

  int Minimum = (int) 1e9, cnt = 0;

  for (auto &it : ord) {
    int rinit = it.first, cinit = it.second;
    bool Evalid = true;

    queue<pair<int, int>> q;
    vector<pair<int, int>> all;
    q.push({rinit, cinit});
    all.push_back({rinit, cinit});
    valid[rinit][cinit] = true;

    while (!q.empty() && Evalid) {
      int r = q.front().first, c = q.front().second;
      q.pop();
      for (int k = 0; k < 4; k++) {
        int rn = r + dr[k], cn = c + dc[k];
        if (isOk(rn, cn) && !valid[rn][cn]) {
          q.push({rn, cn});
          all.push_back({rn, cn});
          valid[rn][cn] = true;
          if (when[rn][cn] < when[rinit][cinit]) {
            Evalid = false;
            break;
          }
        }
      }
    }


    for (auto &it : all) {
      valid[it.first][it.second] = 0;
    }

    if (!Evalid) {
      continue;
    }
    int current = (int) all.size();
    if (current < Minimum) {
      Minimum = current;
      cnt = 0;
    }
    cnt += (Minimum == current);
  }
  cout << Minimum << " " << cnt * Minimum << "\n";
}

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