Submission #1110352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110352		mychecksedad	Virus Experiment (JOI19_virus)	C++17	100 / 100	771 ms	144296 KiB

virus

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 800+10, K = 52, MX = 30;


struct Dsu {
  vector<int> s, p;
  int sz;
  Dsu(int n){
    sz = n;
    s.resize(n+1, 1);
    p.resize(n+1);
    for(int i = 0; i <= n; ++i) p[i] = i;
  }
  int find(int v){
    if(p[v] == v) return v;
    return (p[v] = find(p[v]));
  }
  void merge(int a, int b){
    a = find(a);
    b = find(b);
    if(a != b){
      if(s[a] > s[b]) swap(a, b);
      s[b] += s[a];
      p[a] = b;
      sz--;
    }
  }
};


vector<pii> g[N];
int m, r, c, C[M][M];
string s, t = "WENS";
vector<int> mask(16), to;
vector<int> BLOCK[N];
bool is_key[N], vis[N];
vector<vector<bool>> is(N, vector<bool>(16));

int f(int x, int y){
  return x*c+y;
}
bool check(int x, int y){
  return x >= 0 && y >= 0 && x < r && y < c;
}
int west(int x){
  if(x % c == 0) return 0;
  x--;
  if(check(x / c, x % c)) return vis[x];
  return 0;
}

int east(int x){
  if(x % c == c - 1) return 0;
  x++;
  if(check(x / c, x % c)) return vis[x];
  return 0;
}

int north(int x){
  if(x / c == 0) return 0;
  x -= c;
  if(check(x / c, x % c)) return vis[x];
  return 0;
}

int south(int x){
  if(x / c == r - 1) return 0;
  x += c;
  if(check(x / c, x % c)) return vis[x];
  return 0;
}

int search(int root, vector<int> &is_root, int finish){
  vi used_vis;
  queue<int> q;
  q.push(root);
  vis[root] = 1;
  used_vis.pb(root);
  int sz = 0;
  while(q.size()){
    int v = q.front(); q.pop();
    ++sz;

    for(int k = 0; k < 4; ++k){
      int u = to[k] + v;
      if(vis[u] == 1) continue;
      if(k == 0 && v % c == 0) continue;
      if(k == 1 && v % c == c-1) continue;
      if(k == 2 && v / c == 0) continue;
      if(k == 3 && v / c == r-1) continue;
      if(check(u / c, u % c)){
        if(C[u / c][u % c] == 0) continue;
        // cout << root << ' ' << u << '\n';
        int msk = west(u) + east(u) * 2 + north(u) * 4 + south(u) * 8; //wens
        // cout << msk << '\n';
        if(is[u][msk]){
          vis[u] = 1;
          used_vis.pb(u);
          q.push(u);
          if(finish && is_root[u]){
            for(int &x: used_vis) vis[x] = 0;
            return u;
          }
        }
      }
    }
  }
  for(int &x: used_vis) vis[x] = 0;
    // cout << root << ' '  << sz << '\n';
  if(finish == 0) return sz;
  return -1;
}


void solve(){
  cin >> m >> r >> c >> s;
  for(int i = 0; i < r; ++i){
    for(int j = 0; j < c; ++j){
      cin >> C[i][j];
    }
  }
  to = vi{-1, +1, -c, +c};

  s += s;

  for(int msk = 0; msk < 16; ++msk){
    int cur = 0, mx = 0;
    for(int i = 0; i < s.length(); ++i){
      bool in = 0;
      if(s[i] == 'W' && (1&msk)) in = 1;

      if(s[i] == 'E' && (2&msk)) in = 1;

      if(s[i] == 'N' && (4&msk)) in = 1;

      if(s[i] == 'S' && (8&msk)) in = 1;

      if(in == 1) ++cur;
      else mx=max(mx,cur), cur=0;
    }
    mask[msk] = max(mx,cur);
    if(mask[msk] == 2*m) mask[msk] = MOD;
    // cout << msk << ' ' << mx << '\n';
  }

  for(int i = 0; i < r; ++i){
    for(int j = 0; j < c; ++j){
      int v = f(i, j);
      for(int k = 0; k < 16; ++k){
        if(mask[k] >= C[i][j] && C[i][j] > 0) is[v][k] = 1;
      }
    }
  }

  for(int i = 0; i < r*c; ++i) vis[i] = 0;
  Dsu d(r*c);
  vector<int> is_root(r*c, 1);
  for(int i = 0; i < r; ++i) for(int j = 0; j  < c; ++j) if(C[i][j] == 0) is_root[f(i, j)] = 0; 
  bool OK = true;
  while(OK){
    OK = false;
    vector<pii> P;
    for(int i = 0; i < r*c; ++i){
      if(is_root[i]){
        auto p = search(i, is_root, 1);
        if(p != -1) P.pb({i, p});
      }
    }
    for(auto [u, v]: P){
      if(d.find(u) != d.find(v)){
        // cout << u << ' ' << v << '\n';
        d.merge(u, v);
        is_root[u] = false;
        OK = true;
      }
    }
  }
  int sz = r*c;
  vector<int> good(r*c), SZ(r*c);
  for(int i = 0; i < r*c; ++i){
    if(is_root[i]){
      SZ[i] = search(i, is_root, 0);
      sz = min(sz, SZ[i]);
      good[d.find(i)] = 1;
    }
  }
  int num = 0;
  for(int i = 0; i < r*c; ++i){
    if(is_root[i]){
      if(SZ[i] == sz){
        num += sz;
      }
    }
  }
  cout << sz << ' ' << num;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

Compilation message (stderr)

virus.cpp: In function 'void solve()':
virus.cpp:140:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for(int i = 0; i < s.length(); ++i){
      |                    ~~^~~~~~~~~~~~
virus.cpp: In function 'int main()':
virus.cpp:213:15: warning: unused variable 'aa' [-Wunused-variable]
  213 |   int tt = 1, aa;
      |               ^~

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