#include <bits/stdc++.h>
#define F0R(i, a) for (int i = 0; i < (int)(a); i++)
#define PB push_back
#define MP make_pair
#define F first
#define S second
using namespace std;
typedef pair<int, int> pii;
#define MAXN 640000
char dirchar[4]{ 'N', 'E', 'S', 'W' };
int dr[4]{ -1, 0, 1, 0 };
int dc[4]{ 0, 1, 0, -1 };
int m, r, c;
bool vis[MAXN], on[MAXN];
pii dfspar[MAXN];
int maxseq[16];
int u[800][800];
string s;
int par[MAXN];
vector<pii> nodesin[MAXN];
bool debug = false;
int codefor(pii loc) {
return loc.F * c + loc.S;
}
int root(int node) { return (node == par[node]) ? node : par[node] = root(par[node]); }
bool inBounds(pii loc) {
return loc.F >= 0 && loc.F < r && loc.S >= 0 && loc.S < c && u[loc.F][loc.S] <= 100000;
}
bool infectedby(pii next, int comp) {
int mask = 0;
F0R(d, 4) {
pii indir = MP(next.F + dr[d], next.S + dc[d]);
if (inBounds(indir) && root(codefor(indir)) == root(comp)) {
mask |= 1 << d;
}
}
return maxseq[mask] >= u[next.F][next.S];
}
vector<pii> adjToComp(int comp) {
vector<pii> res;
for (const pii p : nodesin[comp]) {
F0R(d, 4) {
pii next = MP(p.F + dr[d], p.S + dc[d]);
if (inBounds(next) && root(codefor(next)) != root(comp)) {
res.PB(next);
}
}
}
return res;
}
void printcomp(int compid) {
if (!debug) {
return;
}
cout << "contents of component " << compid << ":";
for (const pii p : nodesin[compid]) {
cout << " (" << p.F << ", " << p.S << ")";
}
cout << endl;
}
void join(int a, int b, queue<pii>& q) {
int r1 = root(a), r2 = root(b);
if (r1 == r2) {
return;
}
if (debug) {
cout << "merging comp " << r1 << " with " << r2 << endl;
printcomp(r1);
printcomp(r2);
}
if (nodesin[r1].size() > nodesin[r2].size()) {
swap(r1, r2);
}
vector<pii> adj = adjToComp(r1);
par[r1] = r2;
for (const pii p : nodesin[r1]) {
nodesin[r2].PB(p);
}
for (const pii p : adj) {
if (root(codefor(p)) != r2 && infectedby(p, r2)) {
if (debug) {
cout << "adding " << p.F << " " << p.S << " to queue" << endl;
}
q.push(p);
}
}
if (debug) {
cout << "merged " << r1 << " into " << r2 << endl;
printcomp(r2);
}
}
void preprocess() {
s += s;
F0R(mask, 16) {
int running = 0;
F0R(i, s.size()) {
int dcode = -1;
F0R(j, 4) if (s[i] == dirchar[j]) {
dcode = j;
}
if ((mask >> dcode) & 1) {
running++;
} else {
running = 0;
}
maxseq[mask] = max(maxseq[mask], running);
}
if (maxseq[mask] == (int)s.size()) {
maxseq[mask] = 100000;
}
}
}
void tarjan(pii loc) {
vis[codefor(loc)] = true;
on[codefor(loc)] = true;
if (debug) {
cout << "dfs on loc " << loc.F << " " << loc.S << endl;
int compid = root(codefor(loc));
printf("in comp %d\n", compid);
printcomp(compid);
}
queue<pii> tosearch;
F0R(d, 4) {
pii next = MP(loc.F + dr[d], loc.S + dc[d]);
if (!inBounds(next)) {
continue;
}
if (root(codefor(next)) != root(codefor(loc))) {
if (infectedby(next, root(codefor(loc)))) {
tosearch.push(next);
}
}
}
while (!tosearch.empty()) {
pii next = tosearch.front();
tosearch.pop();
if (root(codefor(next)) == root(codefor(loc))) {
continue;
}
if (vis[codefor(next)]) {
if (on[codefor(next)]) {
pii curr = loc;
while (curr != next) {
pii nextup = dfspar[codefor(curr)];
join(codefor(curr), codefor(nextup), tosearch);
curr = nextup;
}
} else {
continue;
}
} else {
dfspar[codefor(next)] = loc;
tarjan(next);
}
}
on[codefor(loc)] = false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> m >> r >> c;
cin >> s;
F0R(i, r) F0R(j, c) {
cin >> u[i][j];
if (u[i][j] == 0) {
u[i][j] = INT_MAX;
}
}
preprocess();
F0R(i, r) F0R(j, c) if (u[i][j] != INT_MAX) {
int code = codefor(MP(i, j));
par[code] = code;
nodesin[code].PB(MP(i, j));
}
F0R(i, r) F0R(j, c) if (u[i][j] != INT_MAX && !vis[codefor(MP(i, j))]) {
tarjan(MP(i, j));
}
pii res = MP(INT_MAX, 0);
F0R(i, r) F0R(j, c) if (u[i][j] != INT_MAX) {
pii loc = MP(i, j);
if (codefor(loc) == root(codefor(loc))) {
bool terminal = true;
for (const pii p : adjToComp(codefor(loc))) {
if (infectedby(p, codefor(loc))) {
terminal = false;
}
}
if (terminal) {
int curr = nodesin[codefor(loc)].size();
if (curr == res.F) {
res.S += curr;
} else if (curr < res.F) {
res = MP(curr, curr);
}
}
}
}
cout << res.F << "\n" << res.S << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
15616 KB |
Output is correct |
| 2 |
Correct |
402 ms |
46840 KB |
Output is correct |
| 3 |
Correct |
393 ms |
47480 KB |
Output is correct |
| 4 |
Correct |
363 ms |
41720 KB |
Output is correct |
| 5 |
Correct |
414 ms |
42232 KB |
Output is correct |
| 6 |
Correct |
15 ms |
17920 KB |
Output is correct |
| 7 |
Execution timed out |
2087 ms |
49644 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
15360 KB |
Output is correct |
| 2 |
Correct |
26 ms |
15872 KB |
Output is correct |
| 3 |
Correct |
27 ms |
15872 KB |
Output is correct |
| 4 |
Correct |
28 ms |
15872 KB |
Output is correct |
| 5 |
Correct |
26 ms |
15744 KB |
Output is correct |
| 6 |
Correct |
29 ms |
17444 KB |
Output is correct |
| 7 |
Correct |
13 ms |
15488 KB |
Output is correct |
| 8 |
Correct |
26 ms |
16000 KB |
Output is correct |
| 9 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 10 |
Correct |
27 ms |
15872 KB |
Output is correct |
| 11 |
Correct |
15 ms |
15616 KB |
Output is correct |
| 12 |
Incorrect |
18 ms |
16512 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
15616 KB |
Output is correct |
| 2 |
Correct |
402 ms |
46840 KB |
Output is correct |
| 3 |
Correct |
393 ms |
47480 KB |
Output is correct |
| 4 |
Correct |
363 ms |
41720 KB |
Output is correct |
| 5 |
Correct |
414 ms |
42232 KB |
Output is correct |
| 6 |
Correct |
15 ms |
17920 KB |
Output is correct |
| 7 |
Execution timed out |
2087 ms |
49644 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
