Submission #1044286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044286		juicy	Virus Experiment (JOI19_virus)	C++17	100 / 100	398 ms	219616 KiB

virus

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 805, inf = 1e9;
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
const char dr[] = {'N', 'S', 'W', 'E'};

int n, m;
int clr[N * N], str[1 << 4], a[N][N];
bool vis[N * N], in[N * N], del[N * N];
vector<int> scc[N * N], g[N * N];

int id(int i, int j) {
  return (i - 1) * m + j;
}

array<int, 2> pos(int i) {
  int x = (i - 1) / m + 1, y = i - (x - 1) * m;
  return {x, y};
}

bool inside(int i, int j) {
  return 1 <= i && i <= n && 1 <= j && j <= m;
}

void add(int p, int i, int j) {
  if (clr[id(i, j)] == clr[p]) {
    return;
  }
  int mask = 0;
  for (int dr = 0; dr < 4; ++dr) {
    int u = i + dx[dr], v = j + dy[dr];
    if (inside(u, v) && clr[id(u, v)] == clr[p]) {
      mask += 1 << dr;
    }
  }
  if (a[i][j] && str[mask] >= a[i][j]) {
    g[p].push_back(id(i, j));
  }
} 

void ins(int p, vector<int> &ver) {
  for (int x : ver) {
    auto [u, v] = pos(x);
    for (int dr = 0; dr < 4; ++dr) {
      int i = u + dx[dr], j = v + dy[dr];
      if (inside(i, j)) {
        add(p, i, j);
      }
    }
  }
}

vector<int> colors;

void dfs(int u) {
  in[u] = vis[u] = 1;
  colors.push_back(clr[u]);
  for (int i = 0; i < g[u].size(); ++i) {
    int v = g[u][i];
    if (!vis[v]) {
      dfs(v);
      if (clr[u] != colors.back()) {
        for (int x : scc[clr[v]]) {
          in[x] = 0;
        }
        colors.pop_back();
      }
    } else if (in[v]) {
      int c = colors.back();
      colors.pop_back();
      while (clr[v] != c) {
        int o = colors.back();
        colors.pop_back();
        if (scc[c].size() < scc[o].size()) {
          swap(c, o);
        }
        for (int x : scc[o]) {
          clr[x] = c;
        }
        scc[c].insert(scc[c].end(), scc[o].begin(), scc[o].end());
        ins(u, scc[o]);
      }
      colors.push_back(c);
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int S; cin >> S >> n >> m;
  string s; cin >> s;
  s += s;
  for (int mask = 0; mask < (1 << 4); ++mask) {
    int cnt = 0;
    for (int i = 0; i < 2 * S; ++i) {
      int j = find(dr, dr + 4, s[i]) - dr;
      if (mask >> j & 1) {
        ++cnt;
        str[mask] = max(str[mask], cnt);
      } else {
        cnt = 0;
      }
    }
    if (cnt == 2 * S) {
      str[mask] = inf;
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> a[i][j];
      if (a[i][j] == 0) {
        del[id(i, j)] = 1;
      }
    }
  }  
  iota(clr + 1, clr + n * m + 1, 1);
  for (int i = 1; i <= n * m; ++i) {
    if (!del[i]) {
      scc[i].push_back(i);
      ins(i, scc[i]);
    }
  }
  for (int i = 1; i <= n * m; ++i) {
    if (!vis[i] && !del[i]) {
      dfs(i);
      for (int j : scc[clr[i]]) {
        in[j] = 0;
      }
      colors.pop_back();
    }
  }
  int mn = inf, cnt = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (a[i][j]) {
        int u = id(i, j);
        if (clr[u] == u) {
          bool leaf = 1;
          for (int x : scc[u]) {
            for (int v : g[x]) {
              leaf &= clr[v] == u;
            }
          }
          int sz = scc[clr[u]].size();
          if (leaf) {
            if (mn > sz) {
              mn = sz;
              cnt = sz;
            } else if (mn == sz) {
              cnt += sz;
            }
          }
        }
      }
    }
  }
  cout << mn << "\n" << cnt;
  return 0;
}

Compilation message (stderr)

virus.cpp: In function 'void dfs(int)':
virus.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for (int i = 0; i < g[u].size(); ++i) {
      |                   ~~^~~~~~~~~~~~~

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