#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
constexpr unsigned R = 800;
constexpr int di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1};
unsigned r, c;
unsigned u[R][R], component[R][R], infection_time[1 << 4];
bitset<R> visited[R];
bitset<R * R> in_dfs;
vector<unsigned> adj[R * R];
vector<pair<unsigned, unsigned>> component_nodes[R * R];
inline void check_adj_vertices(unsigned i, unsigned j, unsigned x)
{
unsigned mask[4];
mask[0] = 4;
mask[1] = 8;
mask[2] = 1;
mask[3] = 2;
if (infection_time[1] || infection_time[4])
{
if (i - 1 < r && j + 1 < c && component[i - 1][j + 1] == x)
{
mask[0] |= 2;
mask[1] |= 1;
}
if (i + 1 < r && j + 1 < c && component[i + 1][j + 1] == x)
{
mask[1] |= 4;
mask[2] |= 2;
}
if (i + 1 < r && j - 1 < c && component[i + 1][j - 1] == x)
{
mask[2] |= 8;
mask[3] |= 4;
}
if (i - 1 < r && j - 1 < c && component[i - 1][j - 1] == x)
{
mask[3] |= 1;
mask[0] |= 8;
}
if (i - 2 < r && component[i - 2][j] == x)
mask[0] |= 1;
if (i + 2 < r && component[i + 2][j] == x)
mask[2] |= 4;
}
if (j - 2 < c && component[i][j - 2] == x)
mask[3] |= 8;
if (j + 2 < c && component[i][j + 2] == x)
mask[1] |= 2;
for (size_t k = 0; k < 4; k++)
if (i + di[k] < r && j + dj[k] < c && u[i + di[k]][j + dj[k]] <= infection_time[mask[k]] &&
component[i + di[k]][j + dj[k]] != x)
adj[x].emplace_back(component[i + di[k]][j + dj[k]]);
}
unsigned merge_components(unsigned x, unsigned y)
{
if (component_nodes[y].size() > component_nodes[x].size())
swap(x, y);
for (auto const &[i, j] : component_nodes[y])
component[i][j] = x;
for (auto const &[i, j] : component_nodes[y])
check_adj_vertices(i, j, x);
component_nodes[x].insert(component_nodes[x].end(), component_nodes[y].begin(),
component_nodes[y].end());
component_nodes[y].clear();
adj[x].insert(adj[x].end(), adj[y].begin(), adj[y].end());
adj[y].clear();
return x;
}
pair<unsigned, unsigned> find_sccs(unsigned x)
{
in_dfs[x] = 1;
if (component_nodes[x].size() == 1)
check_adj_vertices(x / R, x % R, x), visited[x / R][x % R] = 1;
while (!adj[x].empty())
{
unsigned const y = adj[x].back();
adj[x].pop_back();
if (x == y)
continue;
if (in_dfs[y]) // Merge y into x.
{
unsigned nx = merge_components(x, y);
in_dfs[x] = 0;
return {y, nx};
}
if (visited[y / R][y % R])
continue;
auto [z, ny] = find_sccs(y);
if (z != UINT_MAX)
{
if (z != x)
{
unsigned nx = merge_components(x, ny);
in_dfs[x] = in_dfs[nx] = 0;
return {z, nx};
}
in_dfs[x] = 0;
x = ny;
in_dfs[x] = 1;
}
}
in_dfs[x] = 0;
return {UINT_MAX, x};
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t m;
cin >> m >> r >> c;
string d;
cin >> d;
for (size_t i = 0; i < m; i++)
d[i] = d[i] == 'N' ? 0 : (d[i] == 'E' ? 1 : (d[i] == 'S' ? 2 : 3));
for (size_t j = 0; j < 1 << 4; j++)
{
unsigned longest_conseq = 0;
for (size_t i = 0; i < 2 * m; i++)
{
longest_conseq++;
if (!(j & (1 << d[i % m])))
longest_conseq = 0;
infection_time[j] = max(infection_time[j], longest_conseq);
}
if (longest_conseq == 2 * m)
infection_time[j] = UINT_MAX - 1;
}
for (size_t i = 0; i < r; i++)
for (size_t j = 0; j < c; j++)
{
cin >> u[i][j];
if (!u[i][j])
u[i][j] = UINT_MAX;
}
for (size_t i = 0; i < R; i++)
for (size_t j = 0; j < R; j++)
{
component[i][j] = i * R + j;
if (u[i][j] != UINT_MAX)
component_nodes[i * R + j].emplace_back(i, j);
}
for (size_t i = 0; i < r; i++)
for (size_t j = 0; j < c; j++)
if (!visited[i][j] && u[i][j] != UINT_MAX)
find_sccs(i * R + j);
unsigned min_scc_nodes = UINT_MAX, num_min_sccs = 0;
for (unsigned i = 0; i < r; i++)
for (unsigned j = 0; j < c; j++)
if (!component_nodes[i * R + j].empty())
{
for (auto const &[x, y] : component_nodes[i * R + j])
check_adj_vertices(x, y, i * R + j);
if (!adj[i * R + j].empty())
continue;
if (component_nodes[i * R + j].size() < min_scc_nodes)
min_scc_nodes = component_nodes[i * R + j].size(), num_min_sccs = 1;
else if (component_nodes[i * R + j].size() == min_scc_nodes)
num_min_sccs++;
}
cout << min_scc_nodes << '\n'
<< num_min_sccs * min_scc_nodes << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
53064 KB |
Output is correct |
2 |
Correct |
146 ms |
68660 KB |
Output is correct |
3 |
Correct |
146 ms |
75916 KB |
Output is correct |
4 |
Correct |
148 ms |
75844 KB |
Output is correct |
5 |
Correct |
115 ms |
59176 KB |
Output is correct |
6 |
Correct |
45 ms |
55528 KB |
Output is correct |
7 |
Correct |
223 ms |
86604 KB |
Output is correct |
8 |
Correct |
98 ms |
55416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
52952 KB |
Output is correct |
2 |
Correct |
63 ms |
53160 KB |
Output is correct |
3 |
Correct |
74 ms |
53128 KB |
Output is correct |
4 |
Correct |
75 ms |
53088 KB |
Output is correct |
5 |
Correct |
77 ms |
53116 KB |
Output is correct |
6 |
Correct |
83 ms |
53400 KB |
Output is correct |
7 |
Correct |
48 ms |
52964 KB |
Output is correct |
8 |
Correct |
71 ms |
53196 KB |
Output is correct |
9 |
Correct |
47 ms |
53196 KB |
Output is correct |
10 |
Correct |
74 ms |
53144 KB |
Output is correct |
11 |
Correct |
49 ms |
53120 KB |
Output is correct |
12 |
Correct |
58 ms |
53264 KB |
Output is correct |
13 |
Correct |
76 ms |
53312 KB |
Output is correct |
14 |
Correct |
72 ms |
53364 KB |
Output is correct |
15 |
Correct |
73 ms |
53340 KB |
Output is correct |
16 |
Correct |
85 ms |
53344 KB |
Output is correct |
17 |
Correct |
61 ms |
53280 KB |
Output is correct |
18 |
Correct |
49 ms |
53112 KB |
Output is correct |
19 |
Correct |
74 ms |
53220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
53064 KB |
Output is correct |
2 |
Correct |
146 ms |
68660 KB |
Output is correct |
3 |
Correct |
146 ms |
75916 KB |
Output is correct |
4 |
Correct |
148 ms |
75844 KB |
Output is correct |
5 |
Correct |
115 ms |
59176 KB |
Output is correct |
6 |
Correct |
45 ms |
55528 KB |
Output is correct |
7 |
Correct |
223 ms |
86604 KB |
Output is correct |
8 |
Correct |
98 ms |
55416 KB |
Output is correct |
9 |
Correct |
59 ms |
52952 KB |
Output is correct |
10 |
Correct |
63 ms |
53160 KB |
Output is correct |
11 |
Correct |
74 ms |
53128 KB |
Output is correct |
12 |
Correct |
75 ms |
53088 KB |
Output is correct |
13 |
Correct |
77 ms |
53116 KB |
Output is correct |
14 |
Correct |
83 ms |
53400 KB |
Output is correct |
15 |
Correct |
48 ms |
52964 KB |
Output is correct |
16 |
Correct |
71 ms |
53196 KB |
Output is correct |
17 |
Correct |
47 ms |
53196 KB |
Output is correct |
18 |
Correct |
74 ms |
53144 KB |
Output is correct |
19 |
Correct |
49 ms |
53120 KB |
Output is correct |
20 |
Correct |
58 ms |
53264 KB |
Output is correct |
21 |
Correct |
76 ms |
53312 KB |
Output is correct |
22 |
Correct |
72 ms |
53364 KB |
Output is correct |
23 |
Correct |
73 ms |
53340 KB |
Output is correct |
24 |
Correct |
85 ms |
53344 KB |
Output is correct |
25 |
Correct |
61 ms |
53280 KB |
Output is correct |
26 |
Correct |
49 ms |
53112 KB |
Output is correct |
27 |
Correct |
74 ms |
53220 KB |
Output is correct |
28 |
Correct |
312 ms |
85540 KB |
Output is correct |
29 |
Correct |
375 ms |
85188 KB |
Output is correct |
30 |
Correct |
257 ms |
89676 KB |
Output is correct |
31 |
Correct |
384 ms |
92444 KB |
Output is correct |
32 |
Correct |
333 ms |
93312 KB |
Output is correct |
33 |
Correct |
195 ms |
72712 KB |
Output is correct |
34 |
Correct |
324 ms |
114876 KB |
Output is correct |
35 |
Correct |
247 ms |
79768 KB |
Output is correct |
36 |
Correct |
330 ms |
97580 KB |
Output is correct |
37 |
Correct |
334 ms |
91228 KB |
Output is correct |
38 |
Correct |
271 ms |
93224 KB |
Output is correct |
39 |
Correct |
271 ms |
77084 KB |
Output is correct |
40 |
Correct |
282 ms |
78308 KB |
Output is correct |
41 |
Correct |
140 ms |
71688 KB |
Output is correct |
42 |
Correct |
318 ms |
72384 KB |
Output is correct |
43 |
Correct |
364 ms |
86880 KB |
Output is correct |
44 |
Correct |
133 ms |
55452 KB |
Output is correct |