oj.uz

Submission #958682

# Submission time Handle Problem Language Result Execution time Memory
958682 2024-04-06T10:20:43 Z shenfe1 Virus Experiment (JOI19_virus) C++17
100 / 100
 1445 ms 247300 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

# Verdict Execution time Memory Grader output
1 Correct 18 ms 74584 KB Output is correct
2 Correct 223 ms 144724 KB Output is correct
3 Correct 213 ms 152188 KB Output is correct
4 Correct 232 ms 151880 KB Output is correct
5 Correct 179 ms 131668 KB Output is correct
6 Correct 17 ms 79964 KB Output is correct
7 Correct 504 ms 152232 KB Output is correct
8 Correct 89 ms 102548 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 74328 KB Output is correct
2 Correct 19 ms 74692 KB Output is correct
3 Correct 27 ms 74536 KB Output is correct
4 Correct 19 ms 74496 KB Output is correct
5 Correct 27 ms 72448 KB Output is correct
6 Correct 30 ms 75256 KB Output is correct
7 Correct 15 ms 74188 KB Output is correct
8 Correct 28 ms 74876 KB Output is correct
9 Correct 18 ms 74588 KB Output is correct
10 Correct 18 ms 74496 KB Output is correct
11 Correct 17 ms 74588 KB Output is correct
12 Correct 20 ms 74880 KB Output is correct
13 Correct 28 ms 75008 KB Output is correct
14 Correct 29 ms 74804 KB Output is correct
15 Correct 28 ms 75008 KB Output is correct
16 Correct 30 ms 75008 KB Output is correct
17 Correct 24 ms 74840 KB Output is correct
18 Correct 18 ms 74732 KB Output is correct
19 Correct 28 ms 74744 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 74584 KB Output is correct
2 Correct 223 ms 144724 KB Output is correct
3 Correct 213 ms 152188 KB Output is correct
4 Correct 232 ms 151880 KB Output is correct
5 Correct 179 ms 131668 KB Output is correct
6 Correct 17 ms 79964 KB Output is correct
7 Correct 504 ms 152232 KB Output is correct
8 Correct 89 ms 102548 KB Output is correct
9 Correct 18 ms 74328 KB Output is correct
10 Correct 19 ms 74692 KB Output is correct
11 Correct 27 ms 74536 KB Output is correct
12 Correct 19 ms 74496 KB Output is correct
13 Correct 27 ms 72448 KB Output is correct
14 Correct 30 ms 75256 KB Output is correct
15 Correct 15 ms 74188 KB Output is correct
16 Correct 28 ms 74876 KB Output is correct
17 Correct 18 ms 74588 KB Output is correct
18 Correct 18 ms 74496 KB Output is correct
19 Correct 17 ms 74588 KB Output is correct
20 Correct 20 ms 74880 KB Output is correct
21 Correct 28 ms 75008 KB Output is correct
22 Correct 29 ms 74804 KB Output is correct
23 Correct 28 ms 75008 KB Output is correct
24 Correct 30 ms 75008 KB Output is correct
25 Correct 24 ms 74840 KB Output is correct
26 Correct 18 ms 74732 KB Output is correct
27 Correct 28 ms 74744 KB Output is correct
28 Correct 968 ms 247144 KB Output is correct
29 Correct 1045 ms 231436 KB Output is correct
30 Correct 530 ms 162300 KB Output is correct
31 Correct 807 ms 159944 KB Output is correct
32 Correct 790 ms 161380 KB Output is correct
33 Correct 244 ms 149168 KB Output is correct
34 Correct 1445 ms 201876 KB Output is correct
35 Correct 878 ms 174320 KB Output is correct
36 Correct 770 ms 163636 KB Output is correct
37 Correct 940 ms 188424 KB Output is correct
38 Correct 945 ms 247300 KB Output is correct
39 Correct 285 ms 153184 KB Output is correct
40 Correct 348 ms 154192 KB Output is correct
41 Correct 215 ms 145956 KB Output is correct
42 Correct 890 ms 174932 KB Output is correct
43 Correct 494 ms 159988 KB Output is correct
44 Correct 94 ms 103580 KB Output is correct