Submission #958668

#TimeUsernameProblemLanguageResultExecution timeMemory
958668shenfe1Virus Experiment (JOI19_virus)C++17
6 / 100
454 ms262144 KiB
#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"; } } } set<pair<pii,pii>> st,st1; 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}); st.in({{i,j},{ni,nj}}); } if(a[i][j]!=inf+1&&a[ni][nj]!=inf+1&&valid(ni,nj)&&is[i][j][(1<<((k)%4))]){ // g[ni][nj].pb({i,j}); st1.in({{ni,nj},{i,j}}); } } } } // 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 (stderr)

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;
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...