#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}
#define ll /*long long*/ int
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (640006)
ll k, n, m, grid[801][801];
string S;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int add[]={1<<2,1<<0,1<<1,1<<3};
// N,E,S,W
int gm(char ch) {
if(ch == 'N') return 1<<0;
if(ch == 'E') return 1<<1;
if(ch == 'S') return 1<<2;
return 1<<3;
}
ll best[1<<4];
ll ans[801][801];
ll hsh(ll x,ll y){return x*m + y; }
struct ufds_ {
int p[MAXN], sz[MAXN];
ufds_ () { FOR(i,0,MAXN-1) p[i]=i, sz[i]=1; }
void merge(ll x,ll y){
x=find(x), y=find(y);
if(x==y)return;
assert(~sz[x] && ~sz[y]);
sz[y] += sz[x], sz[x]=0;
p[x]=y;
}
ll find(ll x) { return (p[x]==x)?x:p[x]=find(p[x]); }
bool same(ll a,ll b){return find(a)==find(b);}
} ufds;
ll vis[801][801];
ll vis_cnt;
void join(ll x,ll y){
x=ufds.find(x), y=ufds.find(y);
assert(x!=y);
if(ufds.sz[y] == -1) {
ufds.sz[x] = -1;
return;
}
ufds.merge(x,y);
}
bool bfs(ll x,ll y){
queue<pi> q; vector<pi> all;
ll num=0;
++ vis_cnt;
vis[x][y]=vis_cnt;
q.emplace(x, y); all.eb(x,y);
while(q.size()) {
ll x=q.front().f, y=q.front().s;
q.pop();
++ num;
FOR(i,0,3) {
ll nx=x+dx[i];
ll ny=y+dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m || grid[nx][ny] == 0 || vis[nx][ny] == vis_cnt) continue;
ll mask=0;
FOR(j,0,3) {
ll resx=nx+dx[j];
ll resy=ny+dy[j];
if(resx < 0 || resy < 0 || resx >= n || resy >= m || vis[resx][resy] != vis_cnt) continue;
mask |= add[j];
}
// if(x==1&&y==0 && nx==0&&ny==0) cerr<<mask<<": "<<best[mask]<<"\n";
// cerr<<mask<<" "<<best[mask]<<"\n";
if(grid[nx][ny] > best[mask]) continue;
if(ufds.same(hsh(x,y), hsh(nx,ny))) {
vis[nx][ny]=vis_cnt;
q.emplace(nx,ny); all.eb(nx,ny);
} else {
join(hsh(x,y), hsh(nx,ny));
return 1;
}
}
}
// cerr<<x<<' '<<y<<' '<<num<<"\n";
assert(ufds.find(hsh(x,y)) == hsh(x,y));
ufds.sz[hsh(x, y)] = -1;
for(auto i:all) ans[i.f][i.s] = num;
return 0;
}
int main()
{
FAST
cin>>k>>n>>m>>S;
ll mx=0;
FOR(i,0,n-1) FOR(j,0,m-1) cin>>grid[i][j],mx=max(mx,grid[i][j]);
string tmp=S;
while(S.size() <= mx) {
S+=tmp;
} S+=tmp; assert(S.size() <= (int)3e5);
// cerr<<S<<"\n";
FOR(i,0,(1<<4)-1) {
ll p=0, mx=0;
FOR(j,0,siz(S)-1) {
if(gm(S[j]) & i) ++ p;
else p=0;
mx=max(mx, p);
}
// cerr<<i<<' '<<mx<<'\n';
best[i] = mx;
}
FOR(i,0,n-1) FOR(j,0,m-1) ans[i][j]=1e9;
while(1) {
bool have=0;
FOR(i,0,n-1) FOR(j,0,m-1) if(grid[i][j] && ufds.find(hsh(i,j))==hsh(i,j) && ~ufds.sz[hsh(i,j)]) {
have |= bfs(i, j);
}
if(!have) break;
}
pi anss=pi(1e9,0);
FOR(i,0,n-1) FOR(j,0,m-1) if(ans[i][j] != 1e9) {
if(ans[i][j] < anss.f) anss.f = ans[i][j], anss.s = 1;
else if(ans[i][j] == anss.f) ++ anss.s;
}
cout<<anss.f<<"\n"<<anss.s<<"\n";
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:117:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(S.size() <= mx) {
~~~~~~~~~^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
5624 KB |
Output is correct |
2 |
Correct |
213 ms |
12852 KB |
Output is correct |
3 |
Correct |
228 ms |
13208 KB |
Output is correct |
4 |
Correct |
200 ms |
12920 KB |
Output is correct |
5 |
Correct |
232 ms |
13148 KB |
Output is correct |
6 |
Correct |
14 ms |
11768 KB |
Output is correct |
7 |
Correct |
261 ms |
13428 KB |
Output is correct |
8 |
Correct |
127 ms |
10544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5496 KB |
Output is correct |
2 |
Correct |
11 ms |
5880 KB |
Output is correct |
3 |
Correct |
29 ms |
5876 KB |
Output is correct |
4 |
Correct |
12 ms |
5880 KB |
Output is correct |
5 |
Correct |
29 ms |
5752 KB |
Output is correct |
6 |
Correct |
30 ms |
6260 KB |
Output is correct |
7 |
Correct |
7 ms |
5496 KB |
Output is correct |
8 |
Correct |
29 ms |
6388 KB |
Output is correct |
9 |
Correct |
8 ms |
5752 KB |
Output is correct |
10 |
Correct |
13 ms |
5876 KB |
Output is correct |
11 |
Correct |
8 ms |
5880 KB |
Output is correct |
12 |
Correct |
12 ms |
6008 KB |
Output is correct |
13 |
Correct |
25 ms |
6260 KB |
Output is correct |
14 |
Correct |
24 ms |
6260 KB |
Output is correct |
15 |
Correct |
34 ms |
6260 KB |
Output is correct |
16 |
Correct |
27 ms |
6244 KB |
Output is correct |
17 |
Correct |
20 ms |
6008 KB |
Output is correct |
18 |
Correct |
17 ms |
6008 KB |
Output is correct |
19 |
Correct |
32 ms |
6260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
5624 KB |
Output is correct |
2 |
Correct |
213 ms |
12852 KB |
Output is correct |
3 |
Correct |
228 ms |
13208 KB |
Output is correct |
4 |
Correct |
200 ms |
12920 KB |
Output is correct |
5 |
Correct |
232 ms |
13148 KB |
Output is correct |
6 |
Correct |
14 ms |
11768 KB |
Output is correct |
7 |
Correct |
261 ms |
13428 KB |
Output is correct |
8 |
Correct |
127 ms |
10544 KB |
Output is correct |
9 |
Correct |
7 ms |
5496 KB |
Output is correct |
10 |
Correct |
11 ms |
5880 KB |
Output is correct |
11 |
Correct |
29 ms |
5876 KB |
Output is correct |
12 |
Correct |
12 ms |
5880 KB |
Output is correct |
13 |
Correct |
29 ms |
5752 KB |
Output is correct |
14 |
Correct |
30 ms |
6260 KB |
Output is correct |
15 |
Correct |
7 ms |
5496 KB |
Output is correct |
16 |
Correct |
29 ms |
6388 KB |
Output is correct |
17 |
Correct |
8 ms |
5752 KB |
Output is correct |
18 |
Correct |
13 ms |
5876 KB |
Output is correct |
19 |
Correct |
8 ms |
5880 KB |
Output is correct |
20 |
Correct |
12 ms |
6008 KB |
Output is correct |
21 |
Correct |
25 ms |
6260 KB |
Output is correct |
22 |
Correct |
24 ms |
6260 KB |
Output is correct |
23 |
Correct |
34 ms |
6260 KB |
Output is correct |
24 |
Correct |
27 ms |
6244 KB |
Output is correct |
25 |
Correct |
20 ms |
6008 KB |
Output is correct |
26 |
Correct |
17 ms |
6008 KB |
Output is correct |
27 |
Correct |
32 ms |
6260 KB |
Output is correct |
28 |
Correct |
252 ms |
22916 KB |
Output is correct |
29 |
Correct |
236 ms |
18892 KB |
Output is correct |
30 |
Correct |
211 ms |
14836 KB |
Output is correct |
31 |
Correct |
235 ms |
14552 KB |
Output is correct |
32 |
Correct |
302 ms |
14184 KB |
Output is correct |
33 |
Correct |
211 ms |
14328 KB |
Output is correct |
34 |
Correct |
360 ms |
22712 KB |
Output is correct |
35 |
Correct |
205 ms |
16636 KB |
Output is correct |
36 |
Correct |
277 ms |
14704 KB |
Output is correct |
37 |
Correct |
253 ms |
18296 KB |
Output is correct |
38 |
Correct |
236 ms |
22700 KB |
Output is correct |
39 |
Correct |
247 ms |
15700 KB |
Output is correct |
40 |
Correct |
258 ms |
15596 KB |
Output is correct |
41 |
Correct |
178 ms |
14584 KB |
Output is correct |
42 |
Correct |
237 ms |
18792 KB |
Output is correct |
43 |
Correct |
204 ms |
14720 KB |
Output is correct |
44 |
Correct |
120 ms |
12108 KB |
Output is correct |