Submission #958624

#	Time	Username	Problem	Language	Result	Execution time	Memory
958624		shenfe1	Virus Experiment (JOI19_virus)	C++17	14 / 100	539 ms	182944 KiB

virus

#include <bits/stdc++.h>

#pragma optimize("Ofast")
#pragma target("avx2")
#pragma optimize("unroll-loops")

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
#define int ll
#define ull unsigned ll

const int MAX=800*800+10;
const int B=331;
const int maxB=1000;
const int N=810;
const int block=450;
const int inf=1e18;  
const int mod=1e9+7;
const int mod1=1e9+9;
const ld eps=1e-9;

int dx[8]={-1,0,1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};

int binpow(int a,int n){
  if(!n)return 1;
  if(n%2==1)return a*binpow(a,n-1)%mod;
  int k=binpow(a,n/2);
  return k*k%mod;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int m,r,c;
string s;
int b[MAX];
int a[N][N];
int mx[MAX];
bool is[N][N][16];

int bit(int i,int j){
  return (i>>j)&1;
}

bool valid(int x,int y){
  return (1<=x&&x<=r&&1<=y&&y<=c);
}

int use[N][N];
int tin[N][N],fup[N][N],timer;

vector<pii> g[N][N];
vector<pii> g1[N][N];
map<pii,bool> mp[N][N];
pii f[N][N];
int ans=inf;
int out[N][N];

pii get(pii a){
  if(f[a.F][a.S]==a)return a;
  return f[a.F][a.S]=get(f[a.F][a.S]);
}

void unite(int i,int j,int ni,int nj){
  // cout<<"MRG "<<i<<" "<<j<<" "<<ni<<" "<<nj<<"\n";
  out[i][j]+=out[ni][nj];
  out[ni][nj]=0;
  if(sz(g[i][j])<sz(g[ni][nj])){
    swap(g[i][j],g[ni][nj]);
  }
  for(pii x:g[ni][nj]){
    g[i][j].pb(x);
  }
  g[ni][nj].clear();

  if(sz(mp[i][j])<sz(mp[ni][nj])){
    swap(mp[i][j],mp[ni][nj]);
  }
  for(pair<pii,bool> x:mp[ni][nj]){
    mp[i][j][x.F]=1;
  }
  for(pair<pii,bool> x:mp[ni][nj]){
    for(int k=0;k<4;k++){
      int toi=x.F.F+dx[k];
      int toj=x.F.S+dy[k];
      if(mp[i][j].count({toi,toj}))continue;
      int mask=0;
      for(int f=0;f<4;f++){
        int nwi=toi+dx[(f+2)%4];
        int nwj=toj+dy[(f+2)%4];
        if(mp[i][j].count({nwi,nwj})){
          mask+=(1<<f);
        }
      }
      if(is[toi][toj][mask]){
        g[i][j].pb({toi,toj});
        // cout<<"NEW "<<i<<" "<<j<<" "<<toi<<" "<<toj<<"\n";
      }
    }
  }
  f[ni][nj]={i,j};
  mp[ni][nj].clear();
}


void dfs(int i,int j,int pi=-1,int pj=-1){
  // cout<<i<<" "<<j<<"\n";
  use[i][j]=1;
  tin[i][j]=fup[i][j]=++timer;
  while(!g[i][j].empty()){
    pii to=get(g[i][j].back());
    // cout<<i<<" "<<j<<" "<<to.F<<" "<<to.S<<"\n";
    g[i][j].ppb();
    if(!use[to.F][to.S]){
      dfs(to.F,to.S,pi,pj);
      if(fup[to.F][to.S]<=tin[i][j]){
        unite(i,j,to.F,to.S);
      }
      else{
        out[i][j]++;
      }
    }
    else{
      if(tin[to.F][to.S]==inf){
        out[i][j]++;
      }
      else fup[i][j]=min(fup[i][j],tin[to.F][to.S]);
    }
  }
  tin[i][j]=inf;
}

void solve(){
  cin>>m>>r>>c;
  cin>>s;
  s=s+s;

  for(int i=1;i<=r;i++){
    for(int j=1;j<=c;j++){
      cin>>a[i][j];
      if(a[i][j]==0)a[i][j]=inf+1;
    }
  }

  for(int i=0;i<sz(s);i++){
    if(s[i]=='S')b[i]=0;
    if(s[i]=='W')b[i]=1;
    if(s[i]=='N')b[i]=2;
    if(s[i]=='E')b[i]=3;
  }

  for(int mask=0;mask<16;mask++){
    int l=0;
    for(int i=0;i<=sz(s);i++){
      if(i==sz(s)||!bit(mask,b[i])){
        mx[mask]=max(mx[mask],i-1-l+1);
        l=i+1;
      }
    }
    if(mx[mask]==sz(s)){
      mx[mask]=inf;
    }
    // cout<<mask<<" "<<mx[mask]<<"\n";
  }

  for(int i=1;i<=r;i++){
    for(int j=1;j<=c;j++){
      if(a[i][j]==inf+1)continue;
      f[i][j]={i,j};
      mp[i][j][{i,j}]=1;
      for(int mask=0;mask<16;mask++){
        bool good=1;
        for(int k=0;k<4;k++){
          int ni=i+dx[(k+2)%4];
          int nj=j+dy[(k+2)%4];
          if(bit(mask,k)&&!valid(ni,nj)){
            good=0;
          }
        }
        
        if(good&&mx[mask]>=a[i][j]){
          is[i][j][mask]=1;
        }
        // cout<<i<<" "<<j<<" "<<mask<<" "<<mx[mask]<<" "<<is[i][j][mask]<<"\n";
      }
      for(int mask=0;mask<16;mask++){
        for(int k=0;k<4;k++){
          if(bit(mask,k)){
            is[i][j][mask]|=is[i][j][mask-(1<<k)];
          }
        }
      }
    }
  }

  for(int i=1;i<=r;i++){
    for(int j=1;j<=c;j++){
      for(int k=0;k<4;k++){
        int ni=i+dx[k];
        int nj=j+dy[k];
        if(a[ni][nj]!=inf+1&&valid(ni,nj)&&is[i][j][(1<<((k+2)%4))]){
          g[ni][nj].pb({i,j});
          // cout<<ni<<" "<<nj<<" "<<i<<" "<<j<<"\n";
        }
      }
    }
  }
  // cout<<"\n";
  
  for(int i=1;i<=r;i++){
    for(int j=1;j<=c;j++){
      if(!use[i][j]){
        if(a[i][j]!=inf+1)dfs(i,j);
      }
    }
  }
  int cnt=0;
  for(int i=1;i<=r;i++){
    for(int j=1;j<=c;j++){
      if(!mp[i][j].empty()&&!out[i][j]){
        if(sz(mp[i][j])<ans){
          cnt=1;
          ans=sz(mp[i][j]);
        }
        else if(sz(mp[i][j])==ans){
          cnt++;
        }
      }
      // cout<<i<<" "<<j<<" "<<sz(mp[i][j])<<" "<<out[i][j]<<"\n";
    }
  }
  cout<<ans<<"\n";
  cout<<cnt*ans<<"\n";

}

signed main(){
  // freopen("triangles.in","r",stdin);
  // freopen("triangles.out","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // prec();
  int t=1;
  // cin>>t;
  while(t--)solve();
}

Compilation message (stderr)

virus.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
virus.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      | 
virus.cpp:5: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    5 | #pragma optimize("unroll-loops")
      |

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