oj.uz

답안 #958670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958670 2024-04-06T10:08:37 Z shenfe1 바이러스 (JOI19_virus) C++17
100 / 100
 1371 ms 242260 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=1e9;  
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];
  
  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})||!valid(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";
  sort(all(g[i][j]));
  reverse(all(g[i][j]));
  use[i][j]=1;
  tin[i][j]=fup[i][j]=++timer;
  while(!g[i][j].empty()){
    pii to=get(g[i][j].back());
    g[i][j].ppb();
    if(!use[to.F][to.S]){
      dfs(to.F,to.S);
      fup[i][j]=min(fup[i][j],fup[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],l);
        l=0;
      }
      else l++;
    }
    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(good&&mx[mask]>=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<<"\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")
      | 
virus.cpp: In function 'void solve()':
virus.cpp:194:13: warning: unused variable 'm1' [-Wunused-variable]
  194 |         int m1=0;
      |             ^~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 74588 KB Output is correct
2 Correct 213 ms 144716 KB Output is correct
3 Correct 205 ms 152016 KB Output is correct
4 Correct 190 ms 151888 KB Output is correct
5 Correct 171 ms 131668 KB Output is correct
6 Correct 17 ms 79964 KB Output is correct
7 Correct 469 ms 152248 KB Output is correct
8 Correct 84 ms 102384 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 74332 KB Output is correct
2 Correct 18 ms 74492 KB Output is correct
3 Correct 27 ms 74612 KB Output is correct
4 Correct 19 ms 74496 KB Output is correct
5 Correct 27 ms 72416 KB Output is correct
6 Correct 30 ms 75260 KB Output is correct
7 Correct 17 ms 74284 KB Output is correct
8 Correct 28 ms 74752 KB Output is correct
9 Correct 18 ms 74588 KB Output is correct
10 Correct 18 ms 74496 KB Output is correct
11 Correct 16 ms 74580 KB Output is correct
12 Correct 19 ms 74840 KB Output is correct
13 Correct 28 ms 75032 KB Output is correct
14 Correct 27 ms 75008 KB Output is correct
15 Correct 28 ms 75264 KB Output is correct
16 Correct 27 ms 74744 KB Output is correct
17 Correct 23 ms 74844 KB Output is correct
18 Correct 18 ms 74588 KB Output is correct
19 Correct 28 ms 74752 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 74588 KB Output is correct
2 Correct 213 ms 144716 KB Output is correct
3 Correct 205 ms 152016 KB Output is correct
4 Correct 190 ms 151888 KB Output is correct
5 Correct 171 ms 131668 KB Output is correct
6 Correct 17 ms 79964 KB Output is correct
7 Correct 469 ms 152248 KB Output is correct
8 Correct 84 ms 102384 KB Output is correct
9 Correct 17 ms 74332 KB Output is correct
10 Correct 18 ms 74492 KB Output is correct
11 Correct 27 ms 74612 KB Output is correct
12 Correct 19 ms 74496 KB Output is correct
13 Correct 27 ms 72416 KB Output is correct
14 Correct 30 ms 75260 KB Output is correct
15 Correct 17 ms 74284 KB Output is correct
16 Correct 28 ms 74752 KB Output is correct
17 Correct 18 ms 74588 KB Output is correct
18 Correct 18 ms 74496 KB Output is correct
19 Correct 16 ms 74580 KB Output is correct
20 Correct 19 ms 74840 KB Output is correct
21 Correct 28 ms 75032 KB Output is correct
22 Correct 27 ms 75008 KB Output is correct
23 Correct 28 ms 75264 KB Output is correct
24 Correct 27 ms 74744 KB Output is correct
25 Correct 23 ms 74844 KB Output is correct
26 Correct 18 ms 74588 KB Output is correct
27 Correct 28 ms 74752 KB Output is correct
28 Correct 937 ms 238684 KB Output is correct
29 Correct 945 ms 240872 KB Output is correct
30 Correct 565 ms 239608 KB Output is correct
31 Correct 841 ms 160060 KB Output is correct
32 Correct 784 ms 160240 KB Output is correct
33 Correct 203 ms 148872 KB Output is correct
34 Correct 1371 ms 198740 KB Output is correct
35 Correct 786 ms 182808 KB Output is correct
36 Correct 743 ms 161588 KB Output is correct
37 Correct 845 ms 187824 KB Output is correct
38 Correct 870 ms 242260 KB Output is correct
39 Correct 280 ms 153840 KB Output is correct
40 Correct 338 ms 155020 KB Output is correct
41 Correct 199 ms 146256 KB Output is correct
42 Correct 768 ms 181588 KB Output is correct
43 Correct 479 ms 160760 KB Output is correct
44 Correct 84 ms 103904 KB Output is correct