#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
const int MAX_R = 810;
struct Cell
{
int x, y;
Cell(int _x = 0, int _y = 0)
{
x = _x;
y = _y;
}
Cell operator + (const Cell &c) const
{
return Cell(x + c.x, y + c.y);
}
};
Cell neib[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int m, r, c;
std::string d;
int u[MAX_R][MAX_R];
void input()
{
std::cin >> m >> r >> c;
std::cin >> d;
for (int i = 1; i <= r; i ++)
for (int j = 1; j <= c; j ++)
std::cin >> u[i][j];
}
int get_index(int i, int j)
{
return (i - 1) * c + j;
}
std::string dir = "NESW";
int comp[MAX_R][MAX_R];
int par[MAX_R * MAX_R];
std::vector < Cell > dsu_comp[MAX_R * MAX_R];
int used[MAX_R][MAX_R];
int lon[(1 << 4) + 1];
int is_dead[MAX_R * MAX_R];
void find_longest(int mask)
{
int cnt = 0;
for (int i = 0; i < m; i ++)
{
for (int j = 0; j < 4; j ++)
{
if (d[i] != dir[j])
continue;
if ((mask & (1 << j)) > 0)
cnt ++;
else
{
lon[mask] = std::max(lon[mask], cnt);
cnt = 0;
}
}
}
lon[mask] = std::max(lon[mask], cnt);
cnt = 0;
}
void init()
{
for (int i = 1; i <= r; i ++)
for (int j = 1; j <= c; j ++)
{
if (u[i][j] == 0)
continue;
par[get_index(i, j)] = get_index(i, j);
comp[i][j] = get_index(i, j);
dsu_comp[get_index(i, j)].push_back(Cell(i, j));
}
d = d + d;
m = 2 * m;
for (int mask = 0; mask < (1 << 4); mask ++)
find_longest(mask);
}
int find_leader(int v)
{
if (v == par[v])
return v;
return (par[v] = find_leader(par[v]));
}
std::pair < int, int > bfs(int s)
{
//std::cout << "start bfs " << endl;
for (Cell cur : dsu_comp[s])
{
used[cur.x][cur.y] = 0;
}
/**std::cout << "USED" << endl;
for (int i = 1; i <= r; i ++, std::cout << endl)
for (int j = 1; j <= c; j ++)
std::cout << used[i][j] << " ";*/
std::queue < Cell > q;
q.push(dsu_comp[s].back());
used[q.front().x][q.front().y] = 1;
int cnt = 0;
while(!q.empty())
{
Cell cur = q.front();
q.pop();
///std::cout << "cell " << cur.x << " " << cur.y << endl;
cnt ++;
for (int i = 0; i < 4; i ++)
{
Cell nb = cur + neib[i];
if (nb.x < 1 || nb.x > r || nb.y < 1 || nb.y > c || u[nb.x][nb.y] == 0)
continue;
int mask = 0;
for (int j = 0; j < 4; j ++)
{
Cell ds = nb + neib[j];
if (ds.x < 1 || ds.x > r || ds.y < 1 || ds.y > c)
continue;
if (used[ds.x][ds.y] == 1)
mask |= (1 << j);
}
///std::cout << "neib: " << nb.x << " " << nb.y << " " << mask << " " << lon[mask] << endl;
if (lon[mask] >= u[nb.x][nb.y])
{
if (find_leader(get_index(nb.x, nb.y)) == s)
{
if (!used[nb.x][nb.y])
{
used[nb.x][nb.y] = 1;
q.push(nb);
}
}
else
{
//std::cout << "fuck here" << endl;
return {1, comp[nb.x][nb.y]};
}
}
}
}
return {-1, cnt};
}
int marked[MAX_R * MAX_R];
void unite(int v, int u)
{
v = find_leader(v);
u = find_leader(u);
if (v == u)
return;
if (is_dead[u])
is_dead[v] = 1;
if (dsu_comp[v].size() > dsu_comp[u].size())
{
for (Cell cur : dsu_comp[u])
{
dsu_comp[v].push_back(cur);
comp[cur.x][cur.y] = v;
}
par[u] = v;
}
else
{
Cell spec = dsu_comp[u].back();
dsu_comp[u].pop_back();
for (Cell cur : dsu_comp[v])
{
dsu_comp[u].push_back(cur);
comp[cur.x][cur.y] = u;
}
par[v] = u;
dsu_comp[u].push_back(spec);
}
}
void union_process()
{
std::pair < int, int > res = {1e9, 0};
int cycle =0 ;
while(true)
{
cycle ++;
//if (cycle == 3)
// break;
std::vector < std :: pair < int, int > > edges;
for (int i = 1; i <= r * c; i ++)
marked[i] = 0;
bool done = true;
for (int i = 1; i <= r * c; i ++)
{
int lead = find_leader(i);
if (lead == 0)
continue;
if (marked[lead] || is_dead[lead])
continue;
done = false;
//std::cout << "start from " << i << endl;
std::pair < int, int > cur = bfs(lead);
//std::cout << "survive bfs " << cur.first << " " << cur.second << endl;
if (cur.first == -1)
{
//std::cout << "kill" << endl;
if (cur.second < res.first) res = {cur.second, 0};
if (cur.second == res.first) res.second += cur.second;
is_dead[lead] = 1;
}
else
{
edges.push_back({i, cur.second});
}
///std::cout << "out " << endl;
}
///std::cout << "fine after cycle " << endl;
if (done)
break;
for (std::pair < int, int > road : edges)
{
//std::cout << "edge " << road.first << " " << road.second << endl;
unite(road.first, road.second);
}
//for (int i = 1; i <= r; i ++, std::cout << endl)
// for (int j = 1; j <= c; j ++)
//std::cout << find_leader(comp[i][j]) << " ";
//exit(0);
}
std::cout << res.first << endl << res.second << endl;
}
void solve()
{
input();
init();
union_process();
}
int main()
{
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
16216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
15964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
16216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
