QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#283627 | #1127. Virus Experiment | Max_s_xaM | 100 ✓ | 101ms | 18388kb | C++14 | 5.3kb | 2023-12-14 23:10:38 | 2023-12-14 23:10:38 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <queue>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXR = 810, MAXN = 64e4 + 10, MAXM = 1e5 + 10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int M, n, m, rs[MAXR][MAXR];
char dir[MAXM << 1];
inline int Tr(char ch) {return (ch == 'N' ? 0 : ch == 'E' ? 1 : ch == 'S' ? 2 : 3);}
int mxlen[18];
inline int C(int i, int j) {return (i - 1) * m + j;}
inline pair <int, int> C(int x) {return make_pair((x + m - 1) / m, (x - 1) % m + 1);}
int fa[MAXN];
int Find(int k) {return k == fa[k] ? k : fa[k] = Find(fa[k]);}
inline void Union(int u, int v)
{
u = Find(u), v = Find(v);
if (u != v) fa[u] = v;
}
int cnd[MAXN], top, mch[MAXN];
int vis[MAXN], idx;
queue < pair <int, int> > q;
inline bool Check(int x, int y)
{
if (x < 1 || x > n || y < 1 || y > m) return 0;
int s = 0;
for (int i = 0; i < 4; i++)
{
int xx = x + dx[i], yy = y + dy[i];
if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
// cout << xx << " " << yy << " " << vis[C(xx, yy)] << "\n";
if (vis[C(xx, yy)] == idx) s ^= (1 << i);
}
// cout << "Check " << x << " " << y << " " << s << " " << idx << "\n";
return mxlen[s] >= rs[x][y];
}
inline pair <int, int> BFS(int st)
{
auto cur = C(st); int x = cur.first, y = cur.second;
int cop = Find(st), sz = 0;
if (rs[x][y] == 2e9) return make_pair(-1, 2e9);
while (!q.empty()) q.pop();
q.push(cur), vis[C(x, y)] = ++idx;
while (!q.empty())
{
cur = q.front(), x = cur.first, y = cur.second, q.pop();
// cout << x << " " << y << " " << idx << "\n";
sz++;
for (int i = 0; i < 4; i++)
{
int xx = x + dx[i], yy = y + dy[i];
if (vis[C(xx, yy)] == idx) continue;
if (!Check(xx, yy)) continue;
if (Find(C(xx, yy)) != cop) return make_pair(C(xx, yy), 0);
q.push(make_pair(xx, yy)), vis[C(xx, yy)] = idx;
}
}
return make_pair(-1, sz);
}
int main()
{
// freopen("tmp.in", "r", stdin);
// freopen("tmp.out", "w", stdout);
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(M), Read(n), Read(m);
Read(dir + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
Read(rs[i][j]);
if (!rs[i][j]) rs[i][j] = 2e9;
}
for (int i = 1; i <= M; i++) dir[i + M] = dir[i];
for (int s = 1; s < 16; s++)
{
int cnt = 0;
for (int i = 1; i <= 2 * M; i++)
if (s & (1 << Tr(dir[i]))) cnt++, mxlen[s] = max(mxlen[s], cnt);
else cnt = 0;
if (mxlen[s] == 2 * M) mxlen[s] = 1e9;
}
for (int i = 1; i <= n * m; i++) fa[i] = i;
while (1)
{
top = 0;
for (int i = 1; i <= n * m; i++)
if (fa[i] == i) cnd[++top] = i;
for (int i = 1; i <= top; i++) mch[cnd[i]] = BFS(cnd[i]).first;//, cout << cnd[i] << " " << mch[cnd[i]] << "\n";
bool flag = 0;
for (int i = 1; i <= top; i++)
if (~mch[cnd[i]]) Union(cnd[i], mch[cnd[i]]), flag = 1;
if (!flag) break;
}
int mn = 1e9, ans = 0;
for (int i = 1; i <= n * m; i++)
if (fa[i] == i)
{
auto cur = BFS(i);
if (cur.second < mn) mn = ans = cur.second;
else if (cur.second == mn) ans += cur.second;
}
Write(mn, '\n'), Write(ans, '\n');
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 14
Accepted
Test #1:
score: 14
Accepted
time: 4ms
memory: 13800kb
input:
53768 10 50 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...
output:
1 10
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 53ms
memory: 17484kb
input:
10 800 800 WWWWEWWEWW 7 3 7 5 10 6 9 6 5 8 1 10 1 6 6 1 8 9 3 7 1 3 1 4 9 3 4 2 5 4 5 7 8 10 4 6 2 8 7 2 1 5 3 10 9 10 1 7 6 2 1 8 3 4 10 5 3 3 3 9 2 2 6 1 6 5 6 3 7 9 7 5 8 5 4 3 7 6 9 3 4 9 1 2 7 1 3 4 6 10 8 4 4 9 1 2 6 1 4 4 10 6 10 4 1 5 1 8 5 2 1 9 4 10 9 2 7 9 4 1 6 5 1 6 6 10 10 1 3 10 6 4 8...
output:
1 230450
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 22ms
memory: 17368kb
input:
10 800 800 WWWWWWWWWW 15314 11896 14475 25269 31478 32227 37443 24837 1353 32232 8163 3206 34713 17755 6870 20331 29572 19341 12557 36054 14768 990 30502 32464 15439 17070 15514 32216 37546 25514 27706 3028 26652 17247 13171 40866 36133 9550 22005 24048 33764 25331 12936 27462 27217 33096 19096 3919...
output:
1 800
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 25ms
memory: 18388kb
input:
31 800 800 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
1 800
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 82ms
memory: 17420kb
input:
9999 800 800 WWWEEWEEWEWEEEWEEEWWWEWWEEEEEWEEEWWEWWWEWEWEWEEEWWWWWEWEEEEEEWEEWWEWWEEEEWEWWEWWWEEEWWEEWEWWWEWWEWWEEEWWWEWEEWWEWEWWWEWWWEEEWWEEEWWEEEWWWWEWWEWEWWWWEEWEEEWEWWEWEEWEWEEEWEWEEEWWWWEEEEWWWWWWEWWWEWEWWWEWEWWWEWWEEEEWWEEEEEWEWEWWWEWEEEEWEEEEWEEWEEEEEWEWWEEEWWEEEWEEEEWWEWWEEWEEWEWWEWWWEWEEEWE...
output:
1 639810
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 13748kb
input:
10 800 1 EWEWWWWWWW 1 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 ...
output:
1 392
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 64ms
memory: 17800kb
input:
100000 800 800 WWEEWEEWEEEWEEWWWWWEEEWWWEEEWEWWEWEEEWWWEEEWEWWWWEEWWEWEEEEEEWWEEEWWWWWWWEWWWEEWWWWWWEEWEWEWEEWEWEWEWWEEEEWEEEEWEWWWWEEEEWWWEWWWEWWEWEWWWEWEWEWWEEEEEEWEEEEEWEEEEEWEEEWEEEEEEEWEWWWEWWWEWWWWEEWWEWEEEWWWWEEEEEEWWWEEEEEWEWEWWEWEEEEEEEWEEWWEWWEEWWEEEEEWWEWEWEEWWEEWEEWEWWWWEEWEWEWEEEEEEEWEW...
output:
800 640000
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 42ms
memory: 16832kb
input:
100000 500 500 EWWWEWEWEEWWEEEEEWWEWEEWEWWEEWEEEWEWWWWEWEWWWEWWEWEEWWWWWWWEEEEEEEEEWEEEEEEWEWWEEEEEEEWWEEEWWWEEWWEWEEWWEWWWWWWWWEWEEEWEWWWEWEWWEEEEEEEWWEEEWWWEEWWEEEWEWEWEWWWEWWWEEEWEEWWWWEWWEWWEWWEEEEWWEEWEEEEWEEWWEEEEWWWEWWWEWEWWEWWWEWEEEEEWWWEWEWEEEWWWEEEWEWWWEEWEWEEEWWWWEWEEWWEEWEEEWEWEWWEWEWWWE...
output:
1 227098
result:
ok 2 lines
Subtask #2:
score: 6
Accepted
Test #9:
score: 6
Accepted
time: 0ms
memory: 13728kb
input:
10 10 10 NNNNSENESS 3 2 0 0 1 3 2 3 1 2 3 3 2 0 5 2 4 0 5 1 5 1 2 3 0 4 4 0 1 0 5 0 1 0 2 4 2 2 0 3 0 1 0 1 4 0 1 4 1 0 3 5 5 0 2 5 3 0 3 4 5 3 1 0 5 4 4 0 4 4 1 0 2 0 5 4 0 2 3 0 4 2 0 2 3 0 2 5 5 4 3 0 2 0 5 4 5 4 0 5
output:
1 33
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 4ms
memory: 13816kb
input:
100000 10 10 NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...
output:
1 10
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 16ms
memory: 15804kb
input:
100000 11 11 SWNESSSWNSEWNSNESSNWEWEWNSNNSWSSWSEEWNENWSWNNEWWSWNSESSEWENNESSENEEEESEESEWENEWSNSNNSSNNSWSNNSNESWEWSENNSESEEWWNESSNNWWSNWNNWNWNWWSEENNNWESSWNWNSEWWNWNNWSWSEWSENSNWNWNNEESSSENWWESSWEESWWENSSENWNNEESWENWSSSWEEWNWEWNNENNWSWEWSNNEESESNWNSEEENWWESSWEEWWSWESSNNEEWWNSSWSNEWSENSNNSENNSSNSSEEEE...
output:
27 27
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 4ms
memory: 13724kb
input:
100000 10 10 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...
output:
1 16
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 16ms
memory: 13876kb
input:
100000 1 1 WWSSSWEEEEESSNSSSSENWSESSNSWWSWESWSEEWSNSSEESSWESNNNENENWEENSSSSSNENESEESEWWSNNWSEWSWNWESSWNWSEESNSWSWENWEWNWESEWSSNSWENEWNNSWEEWWSSSWNSNWWWNSSWSSNSENESENNNENWESSENNEWENWEENWNWSSSWWWSNWESWEESNNNESNNEESNEWSSNNSSWSSESNSNNWENENEWWWSEESNWEWWNWNNSSNEEWSWNSWEESNSNSNEWNNWWWWSSWSWWESWWENSENWNWNWN...
output:
1 1
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 12ms
memory: 13780kb
input:
100000 50 50 ENWNNWEESNSNSSESSWNEWWESNWEENNEEWWEWNNESSSEWSWNWEWSSNEEWNSEWSSWNESWSWESEWWSENEWESEWSWSNNWWESSSWSSSESESNSSNESSSWSNWSSSENSWWNWNWNNNSNSNSEENWESENEENNESENSENNWEEESENWSESWSNWNNNSNSNWWENWEEEWSNWWEWSWNSEEEWEWWNSWNNNWWENSNSWWSNNWESNSSSWWNSEWSNWNEEESSEWEESENEESWSNNWSNESEESWEESNWSEEWWSSWESENESSSE...
output:
2500 2500
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 2ms
memory: 14016kb
input:
100 10 10 NENNWNSNNEWNENENNWWNEWNSNWWSSSNSNESSESWESSNNNNEWSWESNSNWSENWNSESNENWSWEWWWNSNWNWESNSESENNWNNWSSWSNSE 2 1 4 1 4 2 1 3 2 4 1 4 4 4 3 3 4 2 2 1 1 3 1 4 2 2 1 4 2 2 2 3 4 3 3 3 1 2 4 1 2 2 3 4 3 4 4 1 3 4 1 4 4 3 4 4 1 4 4 2 1 4 3 4 1 1 3 3 4 3 4 4 1 2 3 3 2 3 4 4 2 4 2 1 1 3 4 2 4 4 2 1 2 3 4...
output:
1 1
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 16ms
memory: 15928kb
input:
100000 50 2 ESNNNSWNNESEWSWWWSENWENSWSNSENSWSENWWNEENNWWNESWNWSEWSWWNSSWSSNENSWWWEEEEENSNWWNNESEWSSNSEEENWWNWWNEENSENWSWEWWNNWWNESSSNWNWWSEWEESESNEEEWNNWWEEEESWSEWWNNSNENWWSEEWNWSNWWEEWNSNWWWWWNWWNNSENNEWSEWENSSSSNWSSSNWSNSNEWESEESWWSEEWWWNWWNESNSNSSNEEWSSENNNEEENSNEEEESNSWNNESEENNEESNSSWENSWSWSNSEE...
output:
46 46
result:
ok 2 lines
Test #17:
score: 0
Accepted
time: 0ms
memory: 15992kb
input:
100 47 41 WWENEWENESSWWNESSENWNEWESWNWESNWNWSEWNEWNSWENSWSNNSWWNNENEWNWWWSWSSESSNEEWEENWEWNWENENESEENNWWWNSWEW 1 2 1 1 2 10 1 2 1 1 2 8 2 2 1 1 1 8 1 1 1 2 2 9 2 1 1 1 1 9 2 1 2 2 2 9 1 2 2 2 2 1 1 1 2 1 9 1 2 2 2 2 9 2 1 2 2 2 9 2 1 1 2 1 9 1 1 1 2 1 8 1 2 2 1 1 10 2 2 2 1 1 2 2 1 2 10 1 2 2 1 1 10...
output:
28 56
result:
ok 2 lines
Test #18:
score: 0
Accepted
time: 0ms
memory: 13880kb
input:
100000 10 10 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...
output:
1 10
result:
ok 2 lines
Test #19:
score: 0
Accepted
time: 2ms
memory: 13988kb
input:
10 50 50 ESSSSSSSEE 4 2 10 7 7 1 8 1 2 4 8 4 4 2 9 7 3 9 7 3 9 3 4 6 7 2 5 2 4 8 5 2 2 10 10 6 2 1 1 5 10 7 3 10 10 10 6 8 7 7 9 3 9 6 1 7 10 9 8 7 2 1 10 8 4 4 10 8 10 5 2 7 6 6 3 10 2 4 1 3 3 2 8 3 9 1 7 2 3 8 7 7 1 5 3 7 5 2 10 5 1 2 10 1 1 4 1 5 1 10 10 10 10 2 7 5 1 8 8 5 5 3 4 5 1 3 5 6 1 6 8 ...
output:
1 545
result:
ok 2 lines
Test #20:
score: 0
Accepted
time: 0ms
memory: 13880kb
input:
100 50 50 WWWNSWNWWESSSESNEWESENENWESESSEENNWNWNSWESENEEEESWEENWSWWWWNEENEEWSSWNWNWNEESEEENWENSENSESSSWNWSSNSW 1 1 2 1 2 1 1 2 1 2 2 1 2 2 2 1 1 2 2 2 1 8 2 1 2 2 2 1 2 1 1 2 2 2 1 1 1 1 2 1 1 2 1 1 1 2 1 2 2 2 1 2 1 1 1 2 2 1 1 2 2 1 2 1 2 1 2 1 1 1 2173 2 2 1 1 2 1 2 1 2 1 1 2 2 2 2 1 1 1 1 1 1 1 ...
output:
2500 2500
result:
ok 2 lines
Test #21:
score: 0
Accepted
time: 14ms
memory: 13768kb
input:
100000 50 50 WWSNNSSSSSSSWWWSWSNNNNSSNNSSNWWNSSNNNSSSSWSWWSNNSNWSNWNWNWSSWWNWWNNSWWSSSWSNWNWSWWNNNNWSSSNSSNNNSSSNSWSWSWWWWSSNNNSWNSNSSSWSWNNWNSNNWSNWSSSWSWWSWNWSWWNNNSSWWSNWSWSNWNNWNSNSSSNNNNWNSWWWNNSWNWWNNSWWNNWNWSNSSWNWNWWWSNSWSNWNSWSWSNWNNNWNSNSSWWNSNWSWNWNSWNNSSWNSNNWSNSWWWWSSWSNNNNSSWWWWNSWNWSW...
output:
50 50
result:
ok 2 lines
Test #22:
score: 0
Accepted
time: 17ms
memory: 15884kb
input:
100000 50 50 SWSSSNWSNWNNNSNSSSNNSWNNWNWWNSNNNSNNWNNSNWNWSNSWWNSWWNSSWNWNWSWNNSSNNWSWSNNNNWWSNSSSSWSSWWSNNWWSNNWSSSSSSWNNWSWWSWWWWNSNSNWWWSSWWNNSSWSNWNSNSNNSWSWWWNSWWNSNSSNSWSNNSWNWSSNWWSSSNWNWSWSNSNSSWWNNWWWWNNNSWWWNWWNSWWNNWSNNSNNWNSSNWWNNSSNSSNSSSNWSNSSWWWNNNSSWSWNNSNSNWSNSNSSWSSSSWSWNNNNWSWWSNNW...
output:
1 3
result:
ok 2 lines
Test #23:
score: 0
Accepted
time: 17ms
memory: 14044kb
input:
100000 50 50 NNEENENWWNWNNEEWNNWWWWNENNWWNENWNNWNNWWENEENNNEEEWENEENENWNEEEENNEWEWEWNNWNNNEWNWEWNNENWWWWWEENNNNENWWWNENNENENWENNWNWEEEEEWNWWWEWWEWENEENNWEEWWWEEENWNNEENEEEEEWWWWEEEEWWWEEEEWWNNNNEEEWNEWEWENEWEWNEEWNWENWNWEWENNENNWNWEWWENNEWNNNNNNNENNENNNNWEENNNWWWWNNENEEEWNWNWEWNNWNNENWWWWNWNEENWWWEN...
output:
50 50
result:
ok 2 lines
Test #24:
score: 0
Accepted
time: 17ms
memory: 13828kb
input:
100000 50 50 SESWSSWEWEWSWESWEEEWESESSEWEWWSEEEWSESEWSESWWSWEWSSSWSEWESSWSSWSWWWWESEEWEWEWEEEWEEEWWSEEESSEESEEWSESSWEEEWWWSEWSWWSEWSWWEESSWSEEEEEWSSWEWEEESEEWSSWSEWESEWSSEWWSWEWSWESESEEWEEEWESWEESWSESWWSWSWEWESWESEESESSWSESESESSEEWWSSWESEWSWSSSEWWWWSSESSSEESSWWWSEWSSSSESWSSSSEESWSSEWSSSEEESWESWSEEWE...
output:
1 37
result:
ok 2 lines
Test #25:
score: 0
Accepted
time: 6ms
memory: 13832kb
input:
50000 50 49 SNNWEENNESEEEWSESNWSENSSWNWWENENWWEWSEWEEENSNSWEEEESENEEENNSSSESSNEEWSWEWWNSSWNNNSNNNWSSSNEWSSSESWSSWNSSESSNESESWESSWWSEENWENWWENWEWWNNWNWNWEESSSEWWSSSWNSEESWEENNENWEWNNEESSNWSNWSWWWSENWSESSNNNSESNESNSNSWSSNNSNWWEEESESSNNESSWNEENWEESESWSNWNENWNENEEENNSEEESEWENSESWENENSENSWNEEEEWNNSWNNSNN...
output:
3 915
result:
ok 2 lines
Test #26:
score: 0
Accepted
time: 0ms
memory: 13820kb
input:
2000 50 50 NNWSNWWSWNNSNWNNNENWNSWSENSWWSNWNWSSSWNESNSWSENWSNWWSWWENWSWNENWSWENSSSSWNWSNWESWNSNWESSEEEEEESNWNNESENNWNNESNSWNNNNESSWNNENEWSNESSNWNNENEEWWEWNEWNSSWSSSEWEESSNEWSEWNSSSWWSNEWEEWESENNSNSNWSWWENNWNSWSWNESEWNEWESWESSESWNEWNESNNWESSSSENSSSESNWNSNWSNNSESESSSNWNEEWNWSNNWEEWSEWEENSNWSESSESEWENN...
output:
50 1400
result:
ok 2 lines
Test #27:
score: 0
Accepted
time: 17ms
memory: 15796kb
input:
100000 50 50 NNNNSENESSEEWWNSESWWNNEEWSEWSEWNWNEESWNEENWWNNWWEWWNNENNWSWSNNEENWSNSSNSNSSNSSWESWEWSWWSENWNWSENWWWSSESENNWNNWESNWEEESNESSWEWSSNESSEEEEWEWESNSNWEEWNWNSENSSNNESEEWESENENESSNNSWWEWWNWNEWENSNWENWEENNNSWSENWWSWENNWSESNSNSWSSSENSSSENNWWEESENSSNESNNSESNNWNWNEESEWWSEWWESEWSEEWWSSNENSNWWSNEENEW...
output:
1 2262
result:
ok 2 lines
Subtask #3:
score: 80
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #28:
score: 80
Accepted
time: 61ms
memory: 17316kb
input:
100000 800 800 SSENEWWEWNSESESSNSEESSEEWESWESNNWWNSEWENENSSEEWESNWSNENSSSNNWNENENSNWWNENESNWNEWSEWNENNWWWNSSSWENNWWEWSSWNNSSSNNNESEENWWNWSSWNEWSWNSSWEESESWESWSENNNSWNNWNENNWWWWSEWNEWWEWNESNSNSWWSEEESWWWWSNNNEEWNWWEWENSSNNNSSEWWSWENENNNSWESWEEEWWEEENSSSSNEEWNNNWWWWSEEWNWNENSEWEWNEWSESNEWNNENSNWEWNNSN...
output:
640000 640000
result:
ok 2 lines
Test #29:
score: 0
Accepted
time: 24ms
memory: 17284kb
input:
100000 800 800 NNSWSNENNEWNWWWWEWNWWSNEWWWNSNEWEWSEWWSEESEEWENESSWWSWSSNEESENWENNESWNESSSENWSWWNWNSNSSNWSNEWWSENNWWEWNEWEWNNNNEWSNEESESWEESNSWNEWWWWNWWESNWNNESNEWWEENWSSENSSWNEENESSWNSESESWSSSEWSWSWWNEWWSSWNNWEWNENWNESWNESNSWENWSSNNWSNWNSESWNWNEESWNEWWENEWWNSEEEWWSSWNSSESWNENSWSSNWEENNWWENENNSNWENWW...
output:
1 3
result:
ok 2 lines
Test #30:
score: 0
Accepted
time: 30ms
memory: 18012kb
input:
100000 800 800 NWWWNWENNENNNWWEWWWWNEWWEWWWEWENEWNWNNNEWENEWWNWWNEENNWWWENEENNENEENWWNNEWWEEWNWEENEWWENWNENEEWWNENWEEWWNWWWNWENNEEEEEWWWNENEWEEEEENNNWNEENNWNNWNEWWEEENENENNWEWNNWNWNNNEEWEWEEEENEWWENENNENNWWENWNNEWNNEENWEEENENWNWENNWNWWEEENWEEEWNENEWNNNWNEENNNWNEWNNWNEWNNENWNEWNEWNNWWENENWENWENWWEEWE...
output:
800 800
result:
ok 2 lines
Test #31:
score: 0
Accepted
time: 52ms
memory: 18208kb
input:
100000 779 785 NWNNNNWSENEWWNENWSSESSNWSNWWNEWNSWNNEWSWNNEEWWSWNSWWEESWENNWWSSWNNSWSSEENSEWWNNWSSSWNNEESNWWSWWWNEENESWNNENWESNWWWEWSNNSENNEESNSSSESWWWWSESNNWWENNWEWNSEESWESSSSNNSNSWSNNWEEEWNENWWNSNSWWWENNSSWSEWWNNEENWWEEEEEEWWWSNENSWSESNWSNNWSSNESWNWSNEENWSSNENEWWWSSSEWNNNESEESEWSWSWSSWNWWNEEWNNSWWE...
output:
28 2100
result:
ok 2 lines
Test #32:
score: 0
Accepted
time: 37ms
memory: 17480kb
input:
100 791 797 WWWENSWEEWNESSSSSWSEENENNSWENEEWWEWSNNSESNNNESENESNWSSWNSSWWWSSNEEEWWNESNSNWESSNSNESEENSNNEWNSSWSENS 1 3 3 2 1 9 3 1 3 1 1 9 1 3 1 1 3 8 1 2 1 3 2 8 3 3 2 1 3 9 1 1 1 3 2 8 1 3 2 2 1 9 3 2 2 1 3 8 1 1 1 3 2 9 2 2 2 1 2 9 1 1 3 3 3 8 3 3 2 1 3 8 2 2 2 1 3 9 2 2 2 3 1 9 2 1 3 1 3 8 3 1 1 1...
output:
27 27
result:
ok 2 lines
Test #33:
score: 0
Accepted
time: 45ms
memory: 17840kb
input:
10 800 800 EEEEEEESSS 10 1 6 1 6 8 6 4 7 9 2 10 2 10 8 8 1 9 1 1 2 2 2 2 9 4 4 6 10 7 7 1 6 1 2 5 2 10 6 7 10 1 3 10 7 1 9 9 1 6 10 10 2 2 3 2 4 4 1 1 7 8 8 7 9 7 1 2 5 3 3 8 9 2 4 8 2 2 9 4 6 10 3 9 4 5 3 1 1 1 3 10 5 7 8 2 5 4 10 8 7 9 5 8 9 9 1 4 9 10 8 9 8 9 7 7 1 9 10 1 4 2 3 4 7 8 6 10 6 3 3 2...
output:
1 134814
result:
ok 2 lines
Test #34:
score: 0
Accepted
time: 75ms
memory: 18072kb
input:
100 800 800 NWWSSNENSWNNWEWESESWWSNWWSNESEEWWEEENEWWNNSSNNESNWNNNWSSEEEWENWWNSNESWSNWSNWWWSWESNESSESSSESNEWNSSNN 3 2 2 3 2 2 3 3 1 2 1 3 3 1 2 1 3 2 2 2 3 3 1 3 2 1 2 2 2 3 2 1 3 2 1 1 3 1 3 1 2 2 3 3 2 3 3 2 2 1 2 1 2 2 1 1 2 3 1 3 1 3 3 2 1 2 2 1 1 1 1 2 2 3 3 2 1 1 1 1 2 3 1 3 3 1 1 1 2 3 3 1 1 2...
output:
640000 640000
result:
ok 2 lines
Test #35:
score: 0
Accepted
time: 38ms
memory: 17700kb
input:
200 612 800 NSSEWNSWWNSSWNWWEEWSSWSNESWEWSENEWEWNSNWWEWNNWSSNSENWWNWENSSWESENNWNSWENWWSEWNNSWWWEESWNENWEWNWSNWWEWWSENWNENEENWEEWSEWWESWWWWNNWENEEWSSNWSNWEEWWWNESESSWESEWNSNNENSSNEEEEEENENEWWESNWEEESSNWENEWESENWSW 2 1 2 13 2 2 2 2 2 1 2 2 2 2 1 1 1 2 1 2 2 2 1 2 2 1 2 1 1 1 2 2 1 1 1 1 2 1 1 1 1 2 2 ...
output:
489600 489600
result:
ok 2 lines
Test #36:
score: 0
Accepted
time: 101ms
memory: 17984kb
input:
49 800 800 WEEWNNSWSWENSNNWSSESNENNSNSWNSESSSSWWNNSNNEENESWW 2 2 2 2 14194 2 2 1 2 1 13890 2 2 2 6 2 1 6592 14012 7199 2 2 2 1 2 1 2 6313 2 1 2 3 2 1 1 1 2 2 2 2 12166 1 1 1 2 1 1 2 2 1 2 1 1 1 2 1 2 1 2 1 2 2 1 1 1 2 1 1 1 1 2 1 2 2 1 1 1 1 13978 2 1 1 1 1 2 1 1 1 2 2 1 2 1 2 2 1 1 2 2 2 2 2762 435...
output:
768 409344
result:
ok 2 lines
Test #37:
score: 0
Accepted
time: 67ms
memory: 17416kb
input:
100 800 800 SNNSSWNSNWSWNSNWSSSWNESWWENSSNWNEWNEWSEWEESSSSWWNNWWWNNNNSWNWNSSWNSENEWSSWNNNEENWNWNNWNNNWWSNNNNWNSS 1 2 2 2 2 1 1 2 2 2 2 2 2 2 1 2 2 1 2 1 1 2 2 2 2 1 2 2 2 2 1 1 2 1 1 1 2 1 2 1 1 2 1 1 1 2 1 1 2 1 1 2 1 1 2 2 2 2 2 1 1 2 2 1 1 1 1 1 2 2 1 1 2 2 2 2 2 1 1 1 1 1 2 1 1 2 2 1 1 1 2 33834...
output:
225000 450000
result:
ok 2 lines
Test #38:
score: 0
Accepted
time: 34ms
memory: 17308kb
input:
800 800 800 NSNSNENNNNEWSNNENNSSSEWWSNESEENSWWENNNENEWNSNSNWESEWWESENESWWSWENEWWWWSESSENEWSSSWNSEWWNNWSEESSNNNWEEWEENESESSWENNNSENNEWWNWNEEWSSNNWSSNEWEESSNWWWNESNWSESWSSNENSNSWSSWESNNWNESSESWWSWSNWEEWENNNNENNEWWENEENNSWSNNNSWEEESSNSNSWSNSWENSEWSESENWSEWNNENWWWSNESNWSEWSSSWWENNNNSSSNNENEWWNEEEEESSNEW...
output:
635256 635256
result:
ok 2 lines
Test #39:
score: 0
Accepted
time: 63ms
memory: 17364kb
input:
100000 800 800 WSENNSNEESNNWNEENNSSSSSNWESSSSWEEWNENSNSWSWNNSSSSNSSWNEWESNNESEWESESWWSENEWNWEEEWESNWSWNNSENEEWENNSSWENESNEEENESSWESNNWESENWWENNWNESWSSEWNWENEWENSNWNWNESEWSNNNWNSSEWNNSWWSESENNSSEEWENWWWEWWSNSEEWESSNESESWWNWWESNSESEWSWNNNEWWNWWEEWWSNNWESWNENSEWSWWNSENWEWSEENEESNNEWWNNNNEEWESESNNSSWEEN...
output:
2 210940
result:
ok 2 lines
Test #40:
score: 0
Accepted
time: 82ms
memory: 17484kb
input:
100000 800 800 NEWNNNSEWNEWNEWWSWSWNNNWWNSESWEWSEWNNSWWNSWWEWWWNSSSWWWNNWWWWSEESNENWEEWNNWNNESEENSNEENSNENWSNENNENEWWWSESSESNESEEEESNEWWSSNEWENWNNENNWSSWENENESNEEEWWEEESNSESSEWWSEWSNSNWWESWWNSSSSWNWEWWSNWSSNNNSNWENWEESWNNNNEWNSWWWSWSWSNNSWNEWEEESNWENSWSWSWSEWSNNNWNNNEEWWWSWNWWWSSWSSSNEWSSEWEWSEWNSES...
output:
4 251772
result:
ok 2 lines
Test #41:
score: 0
Accepted
time: 28ms
memory: 17340kb
input:
50000 800 800 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...
output:
1 53315
result:
ok 2 lines
Test #42:
score: 0
Accepted
time: 92ms
memory: 17840kb
input:
100000 800 749 EWNSSNSNESNNSNSNEWEWSSEWWENWWESNNENWESESSNESEEWWSSSWEESWSESEWENEEWSNNWEENNESESSWNNESSENEENEEENSEEEESWNSSSWSSESNWNWESWNWENNEWNWWSNSWNSSWNNSNSESNESWSNSSWEESSNWSWWSEWNWWENWWNNESSWNSNSWEWNNWNNWSNNEWEWNSSNSSENWWESNSSSNWENNWNEWNESSESSNWNESWWNNSSEWSWWWSENNNNEWSNESENNEENENWSWWSEWSEWSNSNNWEESE...
output:
1 1767
result:
ok 2 lines
Test #43:
score: 0
Accepted
time: 40ms
memory: 17936kb
input:
100000 800 800 SNSWWNNSSSWNWNNNSSWWWNSSWWSWWWWWWWSSNNNSWNNSNNSWNSNWNNSSWWSWSWWNSNWNSWNSSNSWWWNSSWWSSSWWSNNNNSNNNWSSWNWNSSSSNSNWSSNSSSSNSSWSSWWWNSNWNNSSNSNNNWNSNNWWNNNNWWSNWSSWSSWWNSSSWSWSWWSSSNNSNNNNWSWWSSNWSSSNWWWWNNWWSSWWNWNSNSWSNSWWWWNWWSNNNNWWSWWNWNSWWNNSNSWNNNSWWSNNNNNSWWWNSSNSNNWNNWNNSNSWSNWWW...
output:
1 1054
result:
ok 2 lines
Test #44:
score: 0
Accepted
time: 47ms
memory: 17296kb
input:
100000 500 500 SSENEWWEWNSESESSNSEESSEEWESWESNNWWNSEWENENSSEEWESNWSNENSSSNNWNENENSNWWNENESNWNEWSEWNENNWWWNSSSWENNWWEWSSWNNSSSNNNESEENWWNWSSWNEWSWNSSWEESESWESWSENNNSWNNWNENNWWWWSEWNEWWEWNESNSNSWWSEEESWWWWSNNNEEWNWWEWENSSNNNSSEWWSWENENNNSWESWEEEWWEEENSSSSNEEWNNNWWWWSEEWNWNENSEWEWNEWSESNEWNNENSNWEWNNSN...
output:
1 227231
result:
ok 2 lines