Submission #684313

#	Time	Username	Problem	Language	Result	Execution time	Memory
684313		MilosMilutinovic	Virus Experiment (JOI19_virus)	C++14	100 / 100	1452 ms	20580 KiB

virus

/**
 *    author:  wxhtzdy
 *    created: 20.01.2023 20:24:06
**/
#include <bits/stdc++.h>

using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const string D = "NSWE";
       
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int k, n, m;
  cin >> k >> n >> m;
  string d;
  cin >> d;
  vector<vector<int>> a(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
  vector<vector<int>> id(n, vector<int>(m));
  vector<vector<int>> par(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      id[i][j] = i * m + j;
      par[i][j] = id[i][j];
    }
  }
  vector<int> len(1 << 4);
  for (int mask = 0; mask < (1 << 4); mask++) {
    int bal = 0;
    for (int i = 0; i < k; i++) {
      bool ok = false;
      for (int j = 0; j < 4; j++) {
        if ((mask >> j & 1) && D[j] == d[i]) {
          ok = true;
        }
      }     
      bal = (ok ? bal + 1 : 0);
      len[mask] = max(len[mask], bal);
    }         
    if (len[mask] == k) {
      len[mask] = (int) 1e9;
    } else {
      int L = 0;
      while (L < k) {
        bool ok = false;       
        for (int j = 0; j < 4; j++) {
          if ((mask >> j & 1) && D[j] == d[L]) {
            ok = true;
          }
        }
        if (ok) {
          L += 1;
        } else {
          break;
        }
      }
      int R = k - 1;
      while (R >= 0) {
        bool ok = false;
        for (int j = 0; j < 4; j++) {
          if ((mask >> j & 1) && D[j] == d[R]) {
            ok = true;
          }
        }
        if (ok) {
          R -= 1;
        } else {
          break;
        }
      }
      assert(L <= R);
      len[mask] = max(len[mask], L + (k - 1 - R));   
    }
  }
  function<int(int, int)> Get = [&](int x, int y) {
    return par[x][y] == id[x][y] ? id[x][y] : par[x][y] = Get(par[x][y] / m, par[x][y] % m);
  };
  auto Valid = [&](int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m && a[x][y] != 0;
  };
  vector<vector<int>> v(n, vector<int>(m));
  auto Update = [&](vector<int> q) {
    for (int i = 0; i < (int) q.size(); i++) {
      int x = q[i] / m;
      int y = q[i] % m;
      v[x][y] = (int) q.size();
    }
  };
  for (int iter = 0; iter < 20; iter++) {
    vector<int> f;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (a[i][j] != 0 && Get(i, j) == id[i][j]) {
          f.push_back(id[i][j]);
        }
      }
    }
    vector<vector<bool>> was(n, vector<bool>(m));
    for (int i = 0; i < (int) f.size(); i++) {
      if (was[f[i] / m][f[i] % m]) {
        continue;
      }
      vector<int> que(1, f[i]);
      int idx = -1; 
      for (int b = 0; b < (int) que.size(); b++) {
        int x = que[b] / m;
        int y = que[b] % m;
        was[x][y] = true;
        for (int dir = 0; dir < 4; dir++) {
          int nx = x + dx[dir];
          int ny = y + dy[dir];
          if (Valid(nx, ny) && !was[nx][ny]) {
            int mask = 0;
            if (Valid(nx - 1, ny) && was[nx - 1][ny]) {
              mask ^= (1 << 0);              
            }
            if (Valid(nx + 1, ny) && was[nx + 1][ny]) {
              mask ^= (1 << 1);              
            }    
            if (Valid(nx, ny - 1) && was[nx][ny - 1]) {
              mask ^= (1 << 2);  
            }
            if (Valid(nx, ny + 1) && was[nx][ny + 1]) {
              mask ^= (1 << 3);  
            }
            if (len[mask] >= a[nx][ny]) {
              was[nx][ny] = true;
              que.push_back(id[nx][ny]);
              if (Get(nx, ny) != f[i]) {
                idx = Get(nx, ny);
                break;
              }
            }
          }
        }
        if (idx != -1) {
          break;
        }
      }
      for (auto& p : que) {
        was[p / m][p % m] = false;
      }
      if (idx != -1) { 
        int x = f[i] / m;
        int y = f[i] % m;
        par[x][y] = idx;
      } else {
        Update(que);
      }
    }    
  } 
  int res = (int) 1e9;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (v[i][j] > 0) {
        res = min(res, v[i][j]); 
      }
    }
  }
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (v[i][j] == res) {
        cnt += 1;
      }
    }
  }
  cout << res << " " << cnt << '\n';                                                  
  return 0;
}

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