Submission #598121

#	Time	Username	Problem	Language	Result	Execution time	Memory
598121		cjoa	Virus Experiment (JOI19_virus)	C++17	14 / 100	718 ms	124288 KiB

virus

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <random>
#include <algorithm>
#include <cassert>

using namespace std;

#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(...) DBG2::cprint(#__VA_ARGS__, __LINE__, __VA_ARGS__)
#else
#define DEBUG(...)
#endif

using VI = vector<int>;
using VVI = vector<VI>;

int M, R, C;
string D;
int U[801][801];

int max_runs[1<<4];

const string DIR = "NESW";  // direction wind blows from
int dr[] = {-1,  0, +1,  0};
int dc[] = { 0, +1,  0, -1};


void dfs1(const VVI& G, VI& vis, stack<int>& S, int u) {
   vis[u] = true;
   for (int v : G[u]) {
      if (!vis[v])
         dfs1(G, vis, S, v);
   }
   S.push(u);
}

void dfs2(const VVI& G, VI& vis, VI& comp, int u) {
   vis[u] = true;
   comp.push_back(u);
   for (int v : G[u]) {
      if (!vis[v])
         dfs2(G, vis, comp, v);
   }
}

const int INF = 1e9 + 7;

long long sum_cnt = 0;

VI COMP_IDs;
vector<bool> processed;
int infected_mask[801*801];
int bfs(const VI& sources, VI& vis, int comp_id, VI& ans) {
   queue<int> q;
   for (int src : sources) {
      if (U[src / C][src % C] == 0)
         return INF;
      q.push(src);
      vis[src] = comp_id;
   }

   bool ok = true;
   VI visited_nodes, changed_infected_masks;
   while (!q.empty()) {
      int u = q.front(); q.pop();
      visited_nodes.push_back(u);
   //   assert(cnt < R*C*2);
      int r = u/C, c = u % C;
      for (int d = 0; d < 4; ++d) {
         int nr = r + dr[d], nc = c + dc[d];
         if (nr < 0 or nr >= R or nc < 0 or nc >= C)
            continue;
         if (U[nr][nc] == 0)
            continue;

         int v = nr * C + nc;
         if (infected_mask[v] == 0)
            changed_infected_masks.push_back(v);
         infected_mask[v] |= 1<<((d+2)%4);
         if ( max_runs[ infected_mask[v] ] < U[nr][nc] )
            continue;

         if (processed[COMP_IDs[v]]) {
            ok = false;
            break;
         }

         if (vis[v] != comp_id) {
            q.push(v);
            vis[v] = comp_id;
         }
      }
   }
   
   sum_cnt += visited_nodes.size();

   int res = INF;
   if (ok) {
      res = visited_nodes.size();
      for (int u : visited_nodes)
         ans[u] = min(ans[u], res);
   }

   for (int v : changed_infected_masks)
      infected_mask[v] = 0;
   
   return res;
}

int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(nullptr);

   cin >> M >> R >> C;
   cin >> D;
   for (int r = 0; r < R; ++r)
      for (int c = 0; c < C; ++c)
         cin >> U[r][c];

   D += D;

   auto matches = [](int mask, char c) -> bool {
      size_t d = DIR.find(c);
      assert(d != string::npos);
      return (mask & (1<<d)) != 0;
   };

   for (int mask = (1<<4)-1; mask > 0; --mask) {
      for (int k = 0, run = 0; k <= int(D.size()); k++) {
         if (k == int(D.size()) or not matches(mask, D[k])) {
            max_runs[mask] = max(max_runs[mask], run);
            run = 0;
         }
         else
            ++run;
      }
      if (max_runs[mask] >= M)
         max_runs[mask] = INF;
   // DEBUG(mask, max_runs[mask]);
   }


   const int NUM_NODES = R*C;
   auto NODE_ID = [](int r, int c) -> int {
      return r*C + c;
   };

   VVI G(NUM_NODES);
   for (int r = 0; r < R; ++r) {
      for (int c = 0; c < C; ++c) {
         if (U[r][c] == 0) continue;
         for (int d = 0; d < 4; ++d) {
            if (U[r][c] > max_runs[1<<d])
               continue;
            int pr = r + dr[d], pc = c + dc[d];
            if (pr < 0 or pr >= R or pc < 0 or pc >= C or U[pr][pc] == 0)
               continue;
            G[NODE_ID(pr, pc)].push_back(NODE_ID(r, c));
         }
      }
   }

   VI vis(NUM_NODES, false);
   stack<int> S;

   for (int src = 0; src < NUM_NODES; ++src)
      if (!vis[src])
         dfs1(G, vis, S, src);

   VVI Grev(NUM_NODES);
   for (int u = 0; u < NUM_NODES; ++u)
      for (int v : G[u])
         Grev[v].push_back(u);

   vis = VI(NUM_NODES, false);
   VVI SCC;
   COMP_IDs = VI(NUM_NODES, -1);
   while (!S.empty()) {
      int u = S.top(); S.pop();
      if (!vis[u]) {
         VI comp;
         dfs2(Grev, vis, comp, u);
         int comp_id = SCC.size();
         for (int u : comp)
            COMP_IDs[u] = comp_id;
         SCC.push_back(comp);
      }
   }

// DEBUG(SCC.size());

   auto is_root = [&](int comp_id) -> bool {
      for (int u : SCC[comp_id])
         for (int v : G[u])
            if (COMP_IDs[v] > COMP_IDs[u])
               return false;
      return true;
   };


   int best_count = INF;
   VI ans(NUM_NODES, INF);
   vis = VI(NUM_NODES, INF);
   processed = vector<bool>(SCC.size(), false);

   VI P(SCC.size());
   for (int k = 0; k < (int) SCC.size(); ++k)
      P[k] = k;

   mt19937 gen( 321 );
   shuffle(P.begin(), P.end(), gen);

   for (int comp_id : P) {
      /*
      cerr << comp_id << ":";
      for (int u : SCC[comp_id])
         cerr << " (" << u/C << ',' << u%C << ")";
      cerr << endl;
      */

      if (is_root(comp_id)) {
         int cnt = bfs( SCC[comp_id], vis, comp_id, ans );
      // DEBUG(comp_id, cnt, sum_cnt);
         best_count = min(best_count, cnt);
      }
      processed[comp_id] = true;
   }

   cout << best_count << '\n';
   cout << (best_count < INF ?
              count(ans.begin(), ans.end(), best_count) :
              0) << '\n';

   return 0;
}

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