oj.uz

답안 #958646

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958646 2024-04-06T09:38:20 Z shenfe1 바이러스 (JOI19_virus) C++17
14 / 100
 510 ms 176880 KB 
#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,cnt;
bool bad[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";
  bad[i][j]|=bad[ni][nj];
  bad[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)%4];
        int nwj=toj+dy[(f)%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){
  // 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);
      if(fup[to.F][to.S]<=tin[i][j]){
        unite(i,j,to.F,to.S);
      }
      else{
        bad[i][j]=1;
      }
    }
    else{
      if(tin[to.F][to.S]==inf){
        bad[i][j]=1;
      }
      else fup[i][j]=min(fup[i][j],tin[to.F][to.S]);
    }
  }
  if(tin[i][j]==fup[i][j]&&!bad[i][j]){
    // cout<<i-1<<" "<<j-1<<" "<<sz(mp[i][j])<<"\n";
    if(sz(mp[i][j])<ans){
      ans=sz(mp[i][j]);
      cnt=1;
    }
    else if(sz(mp[i][j])==ans){
      cnt++;
    }
  }
  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]=='N')b[i]=0;
    if(s[i]=='W')b[i]=1;
    if(s[i]=='S')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;
        int m1=0;
        for(int k=0;k<4;k++){
          int ni=i+dx[(k)%4];
          int nj=j+dy[(k)%4];
          if(bit(mask,k)&&!valid(ni,nj)){
            good=0;
          }
          if(bit(mask,k)){
            m1+=(1<<((k)%4));
          }
        }
        
        if(good&&mx[m1]>=a[i][j]){
          is[i][j][mask]=1;
        }
        // cout<<i<<" "<<j<<" "<<mask<<" "<<mx[mask]<<" "<<is[i][j][mask]<<"\n";
      }
    }
  }
 
  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[i][j]!=inf+1&&a[ni][nj]!=inf+1&&valid(ni,nj)&&is[ni][nj][(1<<((k+2)%4))]){
          g[i][j].pb({ni,nj});
          // 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);
      }
    }
  }

  if(ans==inf){
    cout<<"0\n0\n";
    return;
  }
  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

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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 76584 KB Output is correct
2 Correct 214 ms 158020 KB Output is correct
3 Correct 199 ms 164672 KB Output is correct
4 Correct 224 ms 164752 KB Output is correct
5 Correct 173 ms 144464 KB Output is correct
6 Correct 18 ms 90200 KB Output is correct
7 Correct 510 ms 176880 KB Output is correct
8 Correct 90 ms 114424 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 74328 KB Output is correct
2 Correct 20 ms 76728 KB Output is correct
3 Correct 30 ms 76708 KB Output is correct
4 Correct 24 ms 76540 KB Output is correct
5 Correct 29 ms 74496 KB Output is correct
6 Correct 34 ms 79532 KB Output is correct
7 Correct 16 ms 74236 KB Output is correct
8 Correct 30 ms 79032 KB Output is correct
9 Incorrect 18 ms 76912 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 76584 KB Output is correct
2 Correct 214 ms 158020 KB Output is correct
3 Correct 199 ms 164672 KB Output is correct
4 Correct 224 ms 164752 KB Output is correct
5 Correct 173 ms 144464 KB Output is correct
6 Correct 18 ms 90200 KB Output is correct
7 Correct 510 ms 176880 KB Output is correct
8 Correct 90 ms 114424 KB Output is correct
9 Correct 16 ms 74328 KB Output is correct
10 Correct 20 ms 76728 KB Output is correct
11 Correct 30 ms 76708 KB Output is correct
12 Correct 24 ms 76540 KB Output is correct
13 Correct 29 ms 74496 KB Output is correct
14 Correct 34 ms 79532 KB Output is correct
15 Correct 16 ms 74236 KB Output is correct
16 Correct 30 ms 79032 KB Output is correct
17 Incorrect 18 ms 76912 KB Output isn't correct
18 Halted 0 ms 0 KB -