Submission #719840

#	Time	Username	Problem	Language	Result	Execution time	Memory
719840		finn__	Virus Experiment (JOI19_virus)	C++17	100 / 100	384 ms	114876 KiB

virus

#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';
}

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 80 / 80