#pragma GCC optimize("O3")
#define MIN(x,y) (x=min(x,(y)))
#define MAX(x,y) (x=max(x,(y)))
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
const int maxm=2e5+9,maxr=809,maxn=maxr*maxr,inf=1e9,dx[4]={1,0,0,-1},dy[4]={0,-1,1,0};
int m,n,r,c,cl=0,u[maxn],t[1<<4],fa[maxn],sz[maxn],p[maxn],fin[maxn],vis[maxn];
string d;
map<char,int>mp;
void init(int k){REP(i,0,k)fa[i]=i,sz[i]=1;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void unite(int x,int y){
if(sz[x]>sz[y])swap(x,y);
fa[x]=y,sz[y]+=sz[x];
}
bool ok(pii x){return 0<=x.f&&x.f<r&&0<=x.s&&x.s<c;}
main(){
IOS;
mp['N']=0,mp['E']=1,mp['W']=2,mp['S']=3;
cin>>m>>r>>c,n=r*c;
cin>>d;
REP(i,0,r)REP(j,0,c)cin>>u[i*c+j];
d+=d,m+=m;
REP(i,0,1<<4){
int le,ri=0;
while(ri<m){
le=ri;
while(ri<m&&((i>>mp[d[ri]])&1))++ri;
MAX(t[i],ri-le);
++ri;
}
if(t[i]==m)t[i]=inf;
}
init(n);
REP(i,0,n)p[i]=i;
pii res={n,0};
for(int z=1;z<=n;z<<=1){
REP(i,0,r){
REP(j,0,c){
++cl;
int id=i*c+j,b=find(id);
if(u[id]&&p[b]==id&&sz[b]<2*z&&!fin[p[b]]){
assert(sz[b]>=z);
queue<pii>q;
q.push({i,j}),vis[id]=cl;
int cnt=0;
while(!q.empty()){
pii h=q.front();q.pop();
++cnt;
REP(k,0,4){
pii nh={h.f+dx[k],h.s+dy[k]};
int nid=nh.f*c+nh.s;
if(ok(nh)&&u[nid]&&vis[nid]!=cl){
int msk=0;
REP(l,0,4){
pii rh={nh.f+dx[l],nh.s+dy[l]};
if(ok(rh)&&vis[rh.f*c+rh.s]==cl)msk|=1<<3-l;
}
if(u[nid]<=t[msk]){
vis[nid]=cl;
q.push(nh);
int nb=find(nid);
if(b!=nb){
p[b]=p[nb];
unite(b,nb);
goto bot;
}
}
}
}
}
fin[id]=1;
if(cnt==res.f)res.s+=cnt;
else if(cnt<res.f)res={cnt,cnt};
}
bot:;
}
}
}
cout<<res.f<<" "<<res.s<<endl;
}
Compilation message
virus.cpp:30:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
virus.cpp: In function 'int main()':
virus.cpp:70:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
if(ok(rh)&&vis[rh.f*c+rh.s]==cl)msk|=1<<3-l;
~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
632 KB |
Output is correct |
2 |
Correct |
330 ms |
16764 KB |
Output is correct |
3 |
Correct |
284 ms |
19176 KB |
Output is correct |
4 |
Correct |
239 ms |
16644 KB |
Output is correct |
5 |
Correct |
227 ms |
19152 KB |
Output is correct |
6 |
Correct |
1 ms |
380 KB |
Output is correct |
7 |
Correct |
303 ms |
17080 KB |
Output is correct |
8 |
Correct |
138 ms |
8092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
16 ms |
936 KB |
Output is correct |
3 |
Correct |
60 ms |
888 KB |
Output is correct |
4 |
Correct |
16 ms |
888 KB |
Output is correct |
5 |
Correct |
60 ms |
888 KB |
Output is correct |
6 |
Correct |
61 ms |
888 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
60 ms |
888 KB |
Output is correct |
9 |
Correct |
1 ms |
504 KB |
Output is correct |
10 |
Correct |
20 ms |
888 KB |
Output is correct |
11 |
Correct |
3 ms |
376 KB |
Output is correct |
12 |
Correct |
4 ms |
376 KB |
Output is correct |
13 |
Correct |
51 ms |
888 KB |
Output is correct |
14 |
Correct |
54 ms |
900 KB |
Output is correct |
15 |
Correct |
48 ms |
888 KB |
Output is correct |
16 |
Correct |
53 ms |
924 KB |
Output is correct |
17 |
Correct |
33 ms |
760 KB |
Output is correct |
18 |
Correct |
4 ms |
504 KB |
Output is correct |
19 |
Correct |
61 ms |
888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
632 KB |
Output is correct |
2 |
Correct |
330 ms |
16764 KB |
Output is correct |
3 |
Correct |
284 ms |
19176 KB |
Output is correct |
4 |
Correct |
239 ms |
16644 KB |
Output is correct |
5 |
Correct |
227 ms |
19152 KB |
Output is correct |
6 |
Correct |
1 ms |
380 KB |
Output is correct |
7 |
Correct |
303 ms |
17080 KB |
Output is correct |
8 |
Correct |
138 ms |
8092 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
16 ms |
936 KB |
Output is correct |
11 |
Correct |
60 ms |
888 KB |
Output is correct |
12 |
Correct |
16 ms |
888 KB |
Output is correct |
13 |
Correct |
60 ms |
888 KB |
Output is correct |
14 |
Correct |
61 ms |
888 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
60 ms |
888 KB |
Output is correct |
17 |
Correct |
1 ms |
504 KB |
Output is correct |
18 |
Correct |
20 ms |
888 KB |
Output is correct |
19 |
Correct |
3 ms |
376 KB |
Output is correct |
20 |
Correct |
4 ms |
376 KB |
Output is correct |
21 |
Correct |
51 ms |
888 KB |
Output is correct |
22 |
Correct |
54 ms |
900 KB |
Output is correct |
23 |
Correct |
48 ms |
888 KB |
Output is correct |
24 |
Correct |
53 ms |
924 KB |
Output is correct |
25 |
Correct |
33 ms |
760 KB |
Output is correct |
26 |
Correct |
4 ms |
504 KB |
Output is correct |
27 |
Correct |
61 ms |
888 KB |
Output is correct |
28 |
Correct |
335 ms |
14620 KB |
Output is correct |
29 |
Correct |
401 ms |
14636 KB |
Output is correct |
30 |
Correct |
354 ms |
14620 KB |
Output is correct |
31 |
Correct |
326 ms |
15004 KB |
Output is correct |
32 |
Correct |
272 ms |
14908 KB |
Output is correct |
33 |
Correct |
284 ms |
16760 KB |
Output is correct |
34 |
Correct |
365 ms |
14456 KB |
Output is correct |
35 |
Correct |
233 ms |
10904 KB |
Output is correct |
36 |
Correct |
349 ms |
15956 KB |
Output is correct |
37 |
Correct |
336 ms |
14568 KB |
Output is correct |
38 |
Correct |
290 ms |
14200 KB |
Output is correct |
39 |
Correct |
404 ms |
18124 KB |
Output is correct |
40 |
Correct |
407 ms |
18024 KB |
Output is correct |
41 |
Correct |
337 ms |
17056 KB |
Output is correct |
42 |
Correct |
388 ms |
16024 KB |
Output is correct |
43 |
Correct |
370 ms |
17056 KB |
Output is correct |
44 |
Correct |
157 ms |
8092 KB |
Output is correct |