oj.uz

답안 #958669

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958669 2024-04-06T10:08:24 Z shenfe1 바이러스 (JOI19_virus) C++17
20 / 100
 493 ms 262144 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 76636 KB Output is correct
2 Correct 232 ms 158280 KB Output is correct
3 Correct 213 ms 166992 KB Output is correct
4 Correct 208 ms 165344 KB Output is correct
5 Correct 182 ms 146552 KB Output is correct
6 Correct 21 ms 90200 KB Output is correct
7 Correct 493 ms 178408 KB Output is correct
8 Correct 92 ms 115448 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 74328 KB Output is correct
2 Correct 18 ms 76544 KB Output is correct
3 Correct 29 ms 76724 KB Output is correct
4 Correct 19 ms 76544 KB Output is correct
5 Correct 27 ms 74496 KB Output is correct
6 Correct 31 ms 79360 KB Output is correct
7 Correct 15 ms 74328 KB Output is correct
8 Correct 28 ms 79016 KB Output is correct
9 Correct 20 ms 76892 KB Output is correct
10 Correct 22 ms 76716 KB Output is correct
11 Correct 17 ms 76884 KB Output is correct
12 Correct 20 ms 77380 KB Output is correct
13 Correct 29 ms 79020 KB Output is correct
14 Correct 31 ms 79352 KB Output is correct
15 Correct 29 ms 79312 KB Output is correct
16 Correct 28 ms 79104 KB Output is correct
17 Correct 23 ms 78940 KB Output is correct
18 Correct 19 ms 76924 KB Output is correct
19 Correct 29 ms 78848 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 76636 KB Output is correct
2 Correct 232 ms 158280 KB Output is correct
3 Correct 213 ms 166992 KB Output is correct
4 Correct 208 ms 165344 KB Output is correct
5 Correct 182 ms 146552 KB Output is correct
6 Correct 21 ms 90200 KB Output is correct
7 Correct 493 ms 178408 KB Output is correct
8 Correct 92 ms 115448 KB Output is correct
9 Correct 16 ms 74328 KB Output is correct
10 Correct 18 ms 76544 KB Output is correct
11 Correct 29 ms 76724 KB Output is correct
12 Correct 19 ms 76544 KB Output is correct
13 Correct 27 ms 74496 KB Output is correct
14 Correct 31 ms 79360 KB Output is correct
15 Correct 15 ms 74328 KB Output is correct
16 Correct 28 ms 79016 KB Output is correct
17 Correct 20 ms 76892 KB Output is correct
18 Correct 22 ms 76716 KB Output is correct
19 Correct 17 ms 76884 KB Output is correct
20 Correct 20 ms 77380 KB Output is correct
21 Correct 29 ms 79020 KB Output is correct
22 Correct 31 ms 79352 KB Output is correct
23 Correct 29 ms 79312 KB Output is correct
24 Correct 28 ms 79104 KB Output is correct
25 Correct 23 ms 78940 KB Output is correct
26 Correct 19 ms 76924 KB Output is correct
27 Correct 29 ms 78848 KB Output is correct
28 Runtime error 433 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -