Submission #229647

#TimeUsernameProblemLanguageResultExecution timeMemory
229647thebesVirus Experiment (JOI19_virus)C++14
14 / 100
502 ms61176 KiB
#include <bits/stdc++.h> #define DEBUG 1 using namespace std; namespace output{ void __(short x){cout<<x;} void __(unsigned x){cout<<x;} void __(int x){cout<<x;} void __(long long x){cout<<x;} void __(unsigned long long x){cout<<x;} void __(double x){cout<<x;} void __(long double x){cout<<x;} void __(char x){cout<<x;} void __(const char*x){cout<<x;} void __(const string&x){cout<<x;} void __(bool x){cout<<(x?"true":"false");} template<class S,class T> void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");} template<class T> void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class T> void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class T> void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class S,class T> void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} void pr(){cout<<"\n";} template<class S,class... T> void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);} } using namespace output; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<int,char> pic; typedef pair<double,double> pdd; typedef pair<ld,ld> pld; typedef vector<int> vi; typedef vector<ll> vl; #define pb push_back #define fox(i,x,y) for(int i=(x);i<=(y);i++) #define foxr(i,x,y) for(int i=(y);i>=(x);i--) #define F first #define S second const int MN = 808, MM = 1e5+5; int N, M, K, i, j, k, x, y, a[MN][MN], dx[]={-1,1,0,0}, dy[]={0,0,-1,1}, ds[MN*MN], vs[MN*MN], len[1<<4], ans, cnt; string s; char op[]={'N','S','W','E'}; set<char> ok; queue<pii> q; vector<pii> *elem[MN*MN]; inline int id(int x,int y){return (x-1)*M+y;} int fnd(int x){return ds[x]=x==ds[x]?x:fnd(ds[x]);} inline bool flood(int x,int y,int cc){ if(a[x][y]==0) return 0; int msk = 0; for(int i=0;i<4;i++){ int nx=x+dx[i], ny=y+dy[i]; if(nx<1||nx>N||ny<1||ny>M) continue; if(fnd(id(nx,ny))==cc) msk |= (1<<i); } return len[msk]>=a[x][y]; } inline bool con(int x,int y,int cc){ if(a[x][y]==0) return 0; int msk = 0, ok = 0; for(int i=0;i<4;i++){ int nx=x+dx[i], ny=y+dy[i]; if(nx<1||nx>N||ny<1||ny>M) continue; if(fnd(id(nx,ny))==cc) msk |= (1<<i); if(fnd(id(nx,ny))==cc&&flood(nx,ny,fnd(id(x,y)))) ok = 1; } return len[msk]>=a[x][y]&&ok; } void augment(int old,int cc){ // augment vs[old] = 1; set<int> nxt; for(auto cell : *elem[old]){ for(int i=0;i<4;i++){ int nx=cell.F+dx[i], ny=cell.S+dy[i]; if(nx<1||nx>N||ny<1||ny>M) continue; if(fnd(id(nx,ny))==cc||nxt.count(fnd(id(nx,ny)))) continue; if(con(nx,ny,cc)) nxt.insert(fnd(id(nx,ny))); } } if(old!=cc){ // need to merge if(elem[old]->size()>elem[cc]->size()) swap(elem[old],elem[cc]); for(auto v : *elem[old]) elem[cc]->pb(v); elem[old]->clear(); } for(auto v : nxt) ds[v] = cc; for(auto v : nxt) augment(v, cc); } int main(){ cin >> K >> N >> M >> s; for(i=0;i<(1<<4);i++){ int cur = 0; ok.clear(); for(j=0;j<4;j++) if((1<<j)&i) ok.insert(op[j]); for(k=0;k<=100111;k++){ if(ok.count(s[k%K])) cur++; else len[i]=max(len[i],cur), cur=0; } len[i]=max(len[i],cur); } for(i=1;i<=N;i++){ for(j=1;j<=M;j++){ scanf("%d",&a[i][j]); ds[id(i,j)]=id(i,j); elem[id(i,j)]=new vector<pii>(); elem[id(i,j)]->pb({i,j}); } } for(i=1;i<=N;i++){ for(j=1;j<=M;j++){ if(!vs[fnd(id(i,j))]&&a[i][j]) augment(id(i,j),id(i,j)); } } ans = 1<<30; memset(vs,0,sizeof(vs)); for(i=1;i<=N;i++){ for(j=1;j<=N;j++){ if(!a[i][j]) continue; int cur_id = fnd(id(i,j)); if(!vs[cur_id]){ vs[cur_id] = 1; int aug = 0; for(auto v : *elem[cur_id]){ for(k=0;k<4;k++){ int nx=v.F+dx[k], ny=v.S+dy[k]; if(nx<1||nx>N||ny<1||ny>M) continue; if(fnd(id(nx,ny))!=cur_id&&flood(nx,ny,cur_id)) aug = 1; } } if(!aug){ if(elem[cur_id]->size()<ans) ans = cnt = elem[cur_id]->size(); else if(elem[cur_id]->size()==ans) cnt += elem[cur_id]->size(); } } } } printf("%d\n%d\n",ans,cnt); return 0; }

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:147:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(elem[cur_id]->size()<ans)
                        ~~~~~~~~~~~~~~~~~~~~^~~~
virus.cpp:149:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     else if(elem[cur_id]->size()==ans)
                             ~~~~~~~~~~~~~~~~~~~~^~~~~
virus.cpp:118:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...