oj.uz

Submission #597865

# Submission time Handle Problem Language Result Execution time Memory
597865 2022-07-17T02:40:34 Z cjoa Virus Experiment (JOI19_virus) C++17
20 / 100
 2000 ms 133036 KB 
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#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;

int infected_mask[801][801];
int bfs(const VI& sources, VI& vis, const VI& COMP_IDs, 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;
   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 nmask = (infected_mask[nr][nc] |= 1<<((d+2)%4));
         if ( max_runs[nmask] < U[nr][nc] )
            continue;

         int v = nr * C + nc;
         if (COMP_IDs[v] > comp_id) {
            ok = false;
            break;
         }

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

   int res = INF;
   if (ok) {
      res = visited_nodes.size();
      for (int u : visited_nodes)
         ans[u] = min(ans[u], res);
   }
   for (int u : visited_nodes) {
      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;
         infected_mask[nr][nc] = 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;
   VI COMP_IDs(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);
      }
   }

   /*
   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);
   for (int comp_id = int(SCC.size()) - 1; comp_id >= 0; comp_id--) {
      /*
      cerr << comp_id << ":";
      for (int u : SCC[comp_id])
         cerr << " (" << u/C << ',' << u%C << ")";
      cerr << endl;
      */

      int cnt = bfs( SCC[comp_id], vis, COMP_IDs, comp_id, ans );
   //   DEBUG(comp_id, cnt);
      best_count = min(best_count, cnt);
   }

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

   return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 596 KB Output is correct
2 Correct 277 ms 104220 KB Output is correct
3 Correct 322 ms 119580 KB Output is correct
4 Correct 295 ms 120924 KB Output is correct
5 Correct 239 ms 83248 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 248 ms 87648 KB Output is correct
8 Correct 127 ms 33536 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 20 ms 856 KB Output is correct
3 Correct 32 ms 852 KB Output is correct
4 Correct 32 ms 852 KB Output is correct
5 Correct 30 ms 724 KB Output is correct
6 Correct 33 ms 1412 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 31 ms 1040 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 18 ms 852 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 2 ms 980 KB Output is correct
13 Correct 30 ms 1156 KB Output is correct
14 Correct 33 ms 1304 KB Output is correct
15 Correct 36 ms 1424 KB Output is correct
16 Correct 33 ms 1296 KB Output is correct
17 Correct 17 ms 1128 KB Output is correct
18 Correct 3 ms 980 KB Output is correct
19 Correct 30 ms 1272 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 596 KB Output is correct
2 Correct 277 ms 104220 KB Output is correct
3 Correct 322 ms 119580 KB Output is correct
4 Correct 295 ms 120924 KB Output is correct
5 Correct 239 ms 83248 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 248 ms 87648 KB Output is correct
8 Correct 127 ms 33536 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 20 ms 856 KB Output is correct
11 Correct 32 ms 852 KB Output is correct
12 Correct 32 ms 852 KB Output is correct
13 Correct 30 ms 724 KB Output is correct
14 Correct 33 ms 1412 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 31 ms 1040 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 18 ms 852 KB Output is correct
19 Correct 2 ms 980 KB Output is correct
20 Correct 2 ms 980 KB Output is correct
21 Correct 30 ms 1156 KB Output is correct
22 Correct 33 ms 1304 KB Output is correct
23 Correct 36 ms 1424 KB Output is correct
24 Correct 33 ms 1296 KB Output is correct
25 Correct 17 ms 1128 KB Output is correct
26 Correct 3 ms 980 KB Output is correct
27 Correct 30 ms 1272 KB Output is correct
28 Correct 373 ms 133036 KB Output is correct
29 Correct 385 ms 132676 KB Output is correct
30 Correct 291 ms 126488 KB Output is correct
31 Execution timed out 2085 ms 90744 KB Time limit exceeded
32 Halted 0 ms 0 KB -