이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |