oj.uz

Submission #991343

# Submission time Handle Problem Language Result Execution time Memory
991343 2024-06-02T07:03:20 Z shenfe1 Virus Experiment (JOI19_virus) C++17
100 / 100
 1338 ms 242244 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]);
      unite(i,j,to.F,to.S);
    }
    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:189:13: warning: unused variable 'm1' [-Wunused-variable]
  189 |         int m1=0;
      |             ^~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 74588 KB Output is correct
2 Correct 242 ms 146060 KB Output is correct
3 Correct 432 ms 155736 KB Output is correct
4 Correct 151 ms 152960 KB Output is correct
5 Correct 136 ms 135524 KB Output is correct
6 Correct 12 ms 79964 KB Output is correct
7 Correct 452 ms 153588 KB Output is correct
8 Correct 68 ms 103928 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 74332 KB Output is correct
2 Correct 17 ms 74752 KB Output is correct
3 Correct 23 ms 74752 KB Output is correct
4 Correct 15 ms 74752 KB Output is correct
5 Correct 22 ms 72724 KB Output is correct
6 Correct 25 ms 75256 KB Output is correct
7 Correct 12 ms 74584 KB Output is correct
8 Correct 23 ms 74752 KB Output is correct
9 Correct 16 ms 74584 KB Output is correct
10 Correct 14 ms 74752 KB Output is correct
11 Correct 12 ms 74588 KB Output is correct
12 Correct 15 ms 74844 KB Output is correct
13 Correct 26 ms 75016 KB Output is correct
14 Correct 24 ms 75008 KB Output is correct
15 Correct 23 ms 75264 KB Output is correct
16 Correct 22 ms 75000 KB Output is correct
17 Correct 20 ms 75112 KB Output is correct
18 Correct 14 ms 74588 KB Output is correct
19 Correct 23 ms 74752 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 74588 KB Output is correct
2 Correct 242 ms 146060 KB Output is correct
3 Correct 432 ms 155736 KB Output is correct
4 Correct 151 ms 152960 KB Output is correct
5 Correct 136 ms 135524 KB Output is correct
6 Correct 12 ms 79964 KB Output is correct
7 Correct 452 ms 153588 KB Output is correct
8 Correct 68 ms 103928 KB Output is correct
9 Correct 11 ms 74332 KB Output is correct
10 Correct 17 ms 74752 KB Output is correct
11 Correct 23 ms 74752 KB Output is correct
12 Correct 15 ms 74752 KB Output is correct
13 Correct 22 ms 72724 KB Output is correct
14 Correct 25 ms 75256 KB Output is correct
15 Correct 12 ms 74584 KB Output is correct
16 Correct 23 ms 74752 KB Output is correct
17 Correct 16 ms 74584 KB Output is correct
18 Correct 14 ms 74752 KB Output is correct
19 Correct 12 ms 74588 KB Output is correct
20 Correct 15 ms 74844 KB Output is correct
21 Correct 26 ms 75016 KB Output is correct
22 Correct 24 ms 75008 KB Output is correct
23 Correct 23 ms 75264 KB Output is correct
24 Correct 22 ms 75000 KB Output is correct
25 Correct 20 ms 75112 KB Output is correct
26 Correct 14 ms 74588 KB Output is correct
27 Correct 23 ms 74752 KB Output is correct
28 Correct 867 ms 238584 KB Output is correct
29 Correct 871 ms 241008 KB Output is correct
30 Correct 977 ms 239864 KB Output is correct
31 Correct 1028 ms 164620 KB Output is correct
32 Correct 961 ms 160596 KB Output is correct
33 Correct 169 ms 148820 KB Output is correct
34 Correct 1276 ms 198484 KB Output is correct
35 Correct 711 ms 182900 KB Output is correct
36 Correct 710 ms 161620 KB Output is correct
37 Correct 826 ms 187728 KB Output is correct
38 Correct 835 ms 242244 KB Output is correct
39 Correct 261 ms 153848 KB Output is correct
40 Correct 332 ms 155064 KB Output is correct
41 Correct 159 ms 146132 KB Output is correct
42 Correct 762 ms 181516 KB Output is correct
43 Correct 1338 ms 164920 KB Output is correct
44 Correct 78 ms 103928 KB Output is correct