#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <stack>
#include <algorithm>
template<typename T> bool ckmax(T& a, T b) {return a<b?a=b,1:0;}
template<typename T> bool ckmin(T& a, T b) {return b<a?a=b,1:0;}
//id = x*C+y
const int MN=6.4e5+10, MM=1e5+10, dx[]={-1,0,1,0}, dy[]={0,1,0,-1};
const char dir[]="NESW";
const int INF=1e6;
int M, R, C, a[MN], c[MN], cc=1, t[16], d[MN], l[MN], ctr, msz=MN, num, p[MN], r[MN];
bool u[MN], v[MN], out[MN];
char b[MM*2];
std::vector<int> adj[MN], nb[MN], nil;
std::stack<int> st;
int find(int n) {return ~p[n]?p[n]=find(p[n]):n;}
std::vector<int> &merge(int a, int b)
{
a=find(a), b=find(b);
if(a==b) return nil;
if(r[a]<r[b]) std::swap(a, b);
p[b]=a,r[a]+=r[a]==r[b],r[b]=-1;
if(nb[a].size() < nb[b].size()) std::swap(nb[a], nb[b]);
for(auto x:nb[b]) nb[a].push_back(x);
return nb[b];
}
bool inf(int n, int x, int y)//[infect]
{
if(!a[x*C+y]) return 0;
n=find(n);
int v=0;
if(y+1<C && n==find(x*C+y+1)) v|=2;
if(x+1<R && n==find(x*C+C+y)) v|=4;
if(y && n==find(x*C+y-1)) v|=8;
if(x && n==find(x*C-C+y)) v|=1;
return t[v]>=a[x*C+y];
}
void dfs(int x, int y)
{
assert(0 <= x && x < R);
assert(0 <= y && y < C);
int id=x*C+y;
assert(!v[id]);
st.push(id);
u[id]=v[id]=1;
l[id]=d[id]=ctr++;
int nx, ny, nid;
for(int i=0;i<4;++i)
{
nx=x+dx[i],ny=y+dy[i];
if(nx < 0 || R <= nx || ny < 0 || C <= ny)
continue;
adj[id].push_back(nx*C+ny);
}
for(;!adj[id].empty();)
{
nid=adj[id].back(); adj[id].pop_back();
nx=nid/C, ny=nid-nx*C;
if(!inf(id, nx, ny)) continue;//time bottleneck here
if(u[nid])
ckmin(l[id], d[nid]);
else if(v[nid])
out[id]=1;
else
{
dfs(nx, ny);
if(l[nid] == d[nid])
out[id]=1;
else
ckmin(l[id], l[nid]);
}
std::vector<int> &on = merge(id, nid);
for(;!on.empty();on.pop_back())
{
int xv=on.back()/C, yv=on.back()-xv*C;
if(xv) adj[id].push_back((xv-1)*C+yv);
if(yv) adj[id].push_back(xv*C+yv-1);
if(xv+1<R) adj[id].push_back((xv+1)*C+yv);
if(yv+1<C) adj[id].push_back(xv*C+yv+1);
}
}
if(l[id]==d[id])
{
bool good=1;
int sz=0;
for(int x;;)
{
x=st.top(); st.pop();
c[x]=cc;
u[x]=0;
if(out[x])
good=0;
++sz;
if(x==id) break;
}
++cc;
if(good)
{
if(ckmin(msz, sz))
num=sz;
else if(sz==msz)
num+=sz;
}
}
}
int main(void)
{
memset(p, -1, sizeof p);
scanf("%d%d%d", &M, &R, &C);
for(int i=0;i<R*C;++i) nb[i].push_back(i);
scanf(" %s", b);
for(int i=0;i<M;++i)
{
for(int j=0;j<4;++j)
if(b[i]==dir[j])
{
b[i]=j;
break;
}
b[i+M]=b[i];
}
for(int i=0, c;i<16;++i)
{
c=0;
for(int j=0;j<M*2;++j)
{
if(i>>b[j]&1)
++c;
else
ckmax(t[i], c), c=0;
}
ckmax(t[i], c);
assert(c < M || c == 2*M);
if(c==2*M)
t[i]=INF;
}
for(int i=0;i<R*C;++i)
scanf("%d", a+i);
for(int i=0;i<R*C;++i)
if(a[i]&&!v[i])
dfs(i/C, i%C), assert(st.empty());
printf("%d\n%d\n", msz, num);
//for(int i=0;i<R*C;++i) printf("%2d%c", c[i], " \n"[!((i+1)%C)]);
return 0;
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &M, &R, &C);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
virus.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", b);
~~~~~^~~~~~~~~~
virus.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", a+i);
~~~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
33152 KB |
Output is correct |
2 |
Correct |
423 ms |
96632 KB |
Output is correct |
3 |
Correct |
450 ms |
104192 KB |
Output is correct |
4 |
Correct |
394 ms |
101936 KB |
Output is correct |
5 |
Correct |
288 ms |
88564 KB |
Output is correct |
6 |
Correct |
23 ms |
33024 KB |
Output is correct |
7 |
Correct |
430 ms |
101624 KB |
Output is correct |
8 |
Correct |
143 ms |
54136 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
32896 KB |
Output is correct |
2 |
Correct |
25 ms |
33280 KB |
Output is correct |
3 |
Correct |
38 ms |
33280 KB |
Output is correct |
4 |
Correct |
26 ms |
33280 KB |
Output is correct |
5 |
Correct |
39 ms |
33152 KB |
Output is correct |
6 |
Correct |
39 ms |
33656 KB |
Output is correct |
7 |
Correct |
22 ms |
32896 KB |
Output is correct |
8 |
Correct |
37 ms |
33272 KB |
Output is correct |
9 |
Correct |
25 ms |
33280 KB |
Output is correct |
10 |
Correct |
26 ms |
33280 KB |
Output is correct |
11 |
Correct |
24 ms |
33152 KB |
Output is correct |
12 |
Correct |
26 ms |
33280 KB |
Output is correct |
13 |
Correct |
38 ms |
33528 KB |
Output is correct |
14 |
Correct |
37 ms |
33528 KB |
Output is correct |
15 |
Correct |
38 ms |
33536 KB |
Output is correct |
16 |
Correct |
39 ms |
33528 KB |
Output is correct |
17 |
Correct |
32 ms |
33400 KB |
Output is correct |
18 |
Correct |
26 ms |
33280 KB |
Output is correct |
19 |
Correct |
39 ms |
33400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
33152 KB |
Output is correct |
2 |
Correct |
423 ms |
96632 KB |
Output is correct |
3 |
Correct |
450 ms |
104192 KB |
Output is correct |
4 |
Correct |
394 ms |
101936 KB |
Output is correct |
5 |
Correct |
288 ms |
88564 KB |
Output is correct |
6 |
Correct |
23 ms |
33024 KB |
Output is correct |
7 |
Correct |
430 ms |
101624 KB |
Output is correct |
8 |
Correct |
143 ms |
54136 KB |
Output is correct |
9 |
Correct |
23 ms |
32896 KB |
Output is correct |
10 |
Correct |
25 ms |
33280 KB |
Output is correct |
11 |
Correct |
38 ms |
33280 KB |
Output is correct |
12 |
Correct |
26 ms |
33280 KB |
Output is correct |
13 |
Correct |
39 ms |
33152 KB |
Output is correct |
14 |
Correct |
39 ms |
33656 KB |
Output is correct |
15 |
Correct |
22 ms |
32896 KB |
Output is correct |
16 |
Correct |
37 ms |
33272 KB |
Output is correct |
17 |
Correct |
25 ms |
33280 KB |
Output is correct |
18 |
Correct |
26 ms |
33280 KB |
Output is correct |
19 |
Correct |
24 ms |
33152 KB |
Output is correct |
20 |
Correct |
26 ms |
33280 KB |
Output is correct |
21 |
Correct |
38 ms |
33528 KB |
Output is correct |
22 |
Correct |
37 ms |
33528 KB |
Output is correct |
23 |
Correct |
38 ms |
33536 KB |
Output is correct |
24 |
Correct |
39 ms |
33528 KB |
Output is correct |
25 |
Correct |
32 ms |
33400 KB |
Output is correct |
26 |
Correct |
26 ms |
33280 KB |
Output is correct |
27 |
Correct |
39 ms |
33400 KB |
Output is correct |
28 |
Correct |
582 ms |
144220 KB |
Output is correct |
29 |
Correct |
609 ms |
144992 KB |
Output is correct |
30 |
Correct |
450 ms |
102876 KB |
Output is correct |
31 |
Correct |
715 ms |
116572 KB |
Output is correct |
32 |
Correct |
730 ms |
119168 KB |
Output is correct |
33 |
Correct |
548 ms |
104668 KB |
Output is correct |
34 |
Correct |
760 ms |
150624 KB |
Output is correct |
35 |
Correct |
450 ms |
110824 KB |
Output is correct |
36 |
Correct |
781 ms |
122720 KB |
Output is correct |
37 |
Correct |
674 ms |
123220 KB |
Output is correct |
38 |
Correct |
487 ms |
138608 KB |
Output is correct |
39 |
Correct |
576 ms |
104032 KB |
Output is correct |
40 |
Correct |
627 ms |
106460 KB |
Output is correct |
41 |
Correct |
374 ms |
89464 KB |
Output is correct |
42 |
Correct |
478 ms |
114276 KB |
Output is correct |
43 |
Correct |
561 ms |
101852 KB |
Output is correct |
44 |
Correct |
137 ms |
54264 KB |
Output is correct |